Prime sum extended !

Computer Science Level 2

Find the sum of all primes less than 1 million such that they are 1 more than a perfect square.

Note-As an explicit example, 2- which is 1 greater than 1 (a perfect square) is a prime and thus satisfies the above condition.

Inspired by Vighnesh Raut's " Prime sum "


The answer is 29570385.

View wiki
Jayakumar Krishnan by Jayakumar Krishnan , 21, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

14 solutions

Brock Brown
Jan 4, 2015

Runs in about a tenth of a second: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
 
from math import sqrt
def prime(x):
    if x < 2:
        return False
    i = 2
    while i <= sqrt(x):
        if x % i == 0:
            return False
        i+=1
    return True
total = 0
i = 1
while i*i < 1000000:
    if prime(i*i+1):
        total += i*i+1
    i += 1
print "Answer:", total

2 Helpful 0 Interesting 0 Brilliant 0 Confused

C++ Code for the problem: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
 
unsigned long long int sum=0;
int ai,j,count;
for(i=1;i<1000;++i)
{
count=0;
a=i*i+1;
for(j=2;j<a;j++)
{
if(a%j==0)
{
count++;
break;
}
}
if(count==0)
{
cout<<"Such number are : "<<a<<endl;
sum=sum+a;
}
}
cout<<"\n\n\nSum of all such numbers : "<<sum;

The Output will be: 

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
Such numbers are : 
2
5
17
37
101
197
257
401
577
677
1297
1601
2917
3137
4357
5477
7057
8101
8837
12101
13457
14401
15377
15877
16901
17957
21317
22501
24337
25601
28901
30977
32401
33857
41617
42437
44101
50177
52901
55697
57601
62501
65537
67601
69697
72901
78401
80657
90001
93637
98597
106277
115601
122501
147457
148997
156817
160001
164837
176401
184901
190097
193601
197137
215297
217157
220901
224677
240101
246017
287297
295937
309137
324901
331777
341057
352837
401957
404497
414737
417317
427717
454277
462401
470597
476101
484417
490001
495617
509797
512657
547601
562501
577601
583697
608401
614657
665857
682277
739601
746497
792101
820837
828101
846401
864901
876097
894917
902501
921601
933157
972197


Sum of all such numbers : 29570385

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Bill Bell
Dec 9, 2014 
1
2
 
from sympy import isprime
print sum ( filter ( isprime, [ 1 + k ** 2 for k in range ( 1, 1000 ) ] ) )

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Brian Brooks
Dec 7, 2014

Generate all perfect squares +1 < 1e6, filter for primality, and sum. 

def is_prime(n):
    if n <= 3:
        return n >= 2
    if n % 2 == 0 or n % 3 == 0:
        return False
    for i in range (5, int(n ** 0.5) + 1, 6):
        if n % i == 0 or n % (i + 2) == 0:
            return False
    return True

print sum(filter(is_prime, [(x ** 2) + 1 for x in range(1, 1000)]))
1 Helpful 0 Interesting 0 Brilliant 0 Confused
Mharfe Micaroz
Oct 30, 2014 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
from math import sqrt
from sympy import primerange 

def perfect(n):
   if n is 1 or type(sqrt(n)) is type(sqrt(4)): return True
    else: return False

def solver():
   A = primerange(2,1000000)
   S = 0
   for p in A:
    if perfect(p-1) is True:
        S+=p
   return S

Python Code executed only in 1.0132 seconds

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Hasmik Garyaka
Sep 7, 2017

static bool checkPrime(long n) { if (n == 1) return false; if (n == 2 || n == 3) return true; if ((n + 1) % 6 != 0 && ((n - 1) % 6 != 0)) return false; 

        long i = Convert.ToInt64(Math.Sqrt(n));
        for (; i >= 5; i--)
        {
            if ((i + 1) % 6 != 0 && ((i - 1) % 6 != 0)) continue;
            if (n % i == 0)
                return false;
        }
        return true;
    }
0 Helpful 0 Interesting 0 Brilliant 0 Confused

How about a colourful solution :

0 Helpful 0 Interesting 0 Brilliant 0 Confused

PARI/GP ^^

while(prime(i)< 10^7,if( floor(sqrt(prime(i) - 1))-sqrt(prime(i)-1) == 0,s = s + prime(i);print(s));i = i+1);print(s)

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Hunter Killer
Jan 6, 2015

Wolfram Mathematica Code: 

1
2
3
 
primelist = Table[Prime[i], {i, 1, PrimePi[10^6]}];
f[prime_] := If[IntegerQ[Sqrt[prime - 1]], prime, 0]
Total[f /@ primelist]

It take 2.558416 sec to produce output: 29570385

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Ratnadip Kuri
Jan 1, 2015

Using Java: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
public class primesum {

    static boolean isprime(int x)
    {
        boolean t=true;
        for(int i=2;i<Math.sqrt(x);i++)
        {
            if(x%i==0){
                t=false;
                break;
            }else
                t=true;
        }

        return t;
    }
    public static void main(String[] args) {

        int i=1;
        int sum=0;
        int squ=i*i+1;
        for(;squ<1000000;)
        {
            if(isprime(squ))
            {
                sum+=squ;
            }
            i++;
            squ=i*i+1;
        }

        System.out.println("Sum is: "+sum);
    }

}

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Drop TheProblem
Dec 12, 2014 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
 
#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;
int sol;
void nprimo(int a)
{int b=0; int r=sqrt(a);
for(int i=2; i<=r; i++)
if(a%i == 0)
b++;
if(b==0) sol+=a;
}
int main(){
    for(int i=1;i<1000;i++){
    nprimo(i*i+1);
    }
cout<<sol<<endl;
system("pause");
    return 0;
}

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Rajat De
Dec 4, 2014

include<iostream>

using namespace std;

define n 1000000

bool p[1000001]={0}; int main(){ p[0]=1; p[1]=1; for(int i=2;i<1001;i++){ if(p[i]==0){ for(int j=i+i;j<=n;j+=i){ p[j]=1; } } } int sum=0; for(int i=1;i i+1<n;i++){ if(p[i i+1]==0){ sum+=i*i+1; } } cout<<sum; }

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Vivek Sedani
Oct 15, 2014

Try PHP version..

<html> <head> <title>Coding is fun - Vivek Sedani</title> </head> <body> <?php

function isprime($n){

if($n % 2 ==0 or $n == 1){ return false; }

$div = 2; $upto = floor( sqrt($n) );

while ($div <= $upto){

if($n % $div == 0){ return false; }

$div = $div + 1 + $div % 2;

}

return true;

}

$ans = 2; $div = 2;

while ( $div <= 1000){

$temp = $div * $div + 1;

if ( isprime ($temp) ){ $ans = $ans + $temp; }

$div = $div + 2;

}

echo $ans;

?> </body> </html>

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Kenny Lau
Oct 11, 2014

Java code: 

public class brilliant201410111904{
    public static void main(String[] args){
        long sum = 0;
        for(int i=1;i<1000;i++){
            if(isPrime(i*i+1)){
                System.out.println("    "+(i*i+1));
                sum += ((long)(i*i+1));
            }
        }
        System.out.print("    "+sum+"\n    ");
    }
    private static boolean isPrime(int n){
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n%i==0) return false;
        }
        return true;
    }
}

Output: 

2
5
17
37
101
197
257
401
577
677
1297
1601
2917
3137
4357
5477
7057
8101
8837
12101
13457
14401
15377
15877
16901
17957
21317
22501
24337
25601
28901
30977
32401
33857
41617
42437
44101
50177
52901
55697
57601
62501
65537
67601
69697
72901
78401
80657
90001
93637
98597
106277
115601
122501
147457
148997
156817
160001
164837
176401
184901
190097
193601
197137
215297
217157
220901
224677
240101
246017
287297
295937
309137
324901
331777
341057
352837
401957
404497
414737
417317
427717
454277
462401
470597
476101
484417
490001
495617
509797
512657
547601
562501
577601
583697
608401
614657
665857
682277
739601
746497
792101
820837
828101
846401
864901
876097
894917
902501
921601
933157
972197
29570385
Press any key to continue . . .
0 Helpful 0 Interesting 0 Brilliant 0 Confused 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
 
from math import sqrt
def is_prime(n):
    if n in {0,1}:
        return False
    for i in range(2,int(sqrt(n))+1):
        if n%i==0:
            return False
    return True

def good_primes():
    for n in range(2,10**6):
        if not is_prime(n):
            continue
        if sqrt(n-1)%1==0:
            yield n
print(sum(n for n in good_primes()))

You Kad - 4 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...