Prime Sum 2

Let a prime no. p be there such that: p=x^2-1 = (x+1)(x-1)

So, there are two factors , however as p is prime no. one of them must be equal to one.

If x+1=1, => x=0 , =>p=(-1) [Not possible]

If x-1=1, => x=2, =>p=3 [Only possible solution]

3 is the only solution and as all the no. less than 1000 are asked, ans is 3.

Well here's a C++ code for the given problem:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

int a,sum=0,i,j,count;
for(i=2;i<33;++i)
{
count=0;
a=i*i-1;
for(j=2;j<a;j++)
{
if(a%j==0)
{
count++;
break;
}
}
if(count==0)
{
cout<<endl<<"Such number are : "<<a<<", ";
sum=sum+a;
}
}
cout<<"\n\n\nSum of all such numbers : "<<sum;

The Output will be:

1
2
3
4

Such numbers are : 3


Sum of all such numbers : 3

Note that n^2-1 factors as (n-1)(n+1). This obviously cannot be prime unless one of the terms is 1. This occurs when n=2, so the only prime number is 3.

Here's some Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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
def perfect_square(x):
    i = 1
    while i*i <= x:
        if i*i == x:
            return True
        i += 1
    return False
total = 0
for i in xrange(1, 1000):
    if prime(i) and perfect_square(i+1):
        total += i
        print i
print "Answer:", total