Prime Sum

Computer Science Level 2

Find the sum of all the prime numbers less than 1000 that are 1 more than a perfect square.

For example, 2 is a prime that is 1 more than the perfect square 1.

The answer is 2271.

7 solutions

Kenny Lau
Oct 11, 2014

Java code:

public class brilliant201410111910{
    public static void main(String[] args){
        long sum = 0;
        for(int i=1;i<Math.sqrt(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
2271
Press any key to continue . . .

Is there a pattern to classifying $n$ such that $n^2 + 1$ is prime?

For example, we know that if $n > 2$ is odd, then $n^2 + 1$ is even and not prime. This rules out $n = 3, 5, 7, 9, \ldots$ . Similarly, for $n > 3$ and $n \equiv 2, 3 \pmod{5}$ , we get that $n^2 + 1 \equiv 0 \pmod{5}$ . This rules out $n = 8, 12, 18, 22 \ldots$ .

Calvin Lin Staff - 6 years, 8 months ago

Would be nice!

Bill Bell - 6 years, 6 months ago

int s=0,g=0;
double a;
for(int x=1;x<=1000;x++)
{
a=Math.sqrt(x);
double y=(int)a;
if(a==y)
{int n=x+1;
for(int l=2;l<n;l++)
{
if(n%l!=0)
s=1;
else
s=2;
}
if(s==1)
g+=n;
}
}System.out.println(g);

I think it will also work

Chaitnya Shrivastava - 6 years, 8 months ago

Bill Bell
Dec 4, 2014

In Python, using the sympy library:

Forgive me for not writing yet another way of deciding whether a number is prime.

Hans Wurst
Oct 15, 2018

#include <iostream>
using namespace std;

int IsPrime(int number) //test number for primality, return number if prime, 0 if not prime
{
    if (number == 2)
        return number;      //2 is prime
    if (!(number&1) || number<2) //if number is not 2, but is divisible by 2 (LSB==0) OR if number is 1, 0 or negative(<2), end function
        return 0;
    for (int i = 3; i*i <= number; i+=2) //for every odd i from 3 up to sqrt(number) ...
        if (number%i == 0)                  //... if i is a factor, end function
            return 0;

    return number;          //if number survived those tests, it is prime
}

int main(void)
{
    //get the sum of all primes of form p=n^2+1; p<1000
    int sum = 0;
    for (int i = 1; i*i < 999; i++)
        sum += IsPrime(i*i+1);

    cout << "The sum of all primes of the form \"p = n^2+1; p<1000\" is: " << sum << endl;
    cout << "Press enter to end program.";
    cin.ignore();
    return 0;
}

Resha Dwika Hefni Al-Fahsi
Mar 15, 2016

Another Solution

#include<bits/stdc++.h>
using namespace std;

int a,b=0,c;
bool checkprime(int n){
   bool index=true;
   long long i=2;

    if(n==1) index=false;
    if(n==2) index=true; 
        else
        while(i<=(long long)ceil(sqrt(n))){
            if(n%i==0) return index=false;
                i++;
        }

   return index;
}
int main(){
    for(int i=1;i<32;i++){  //because 32^2=1024
        a=pow(i,2); c=a+1;
        if(checkprime(c)==true){
        b=c+b;
        }
    }
    cout<<b<<endl; //It will print 2271
}

Weuler Filho
Aug 21, 2015

C++ solution

    #include <bits/stdc++.h>

    using namespace std;

    int main () {
        int sm = 0;
        for (int i=1; i * i + 1< 1000; i++) {
            int dvs=2;

            int num = i*i + 1;
            int nm = num;
            int k = 2;
            while (num > 0 && k*k < nm) {
                if (num%k == 0) {
                    num /= k;
                    dvs++;
                }
                k++;
            }
            if (dvs == 2) sm +=nm;
        }

        cout << sm << endl;

    }

Trung Đặng Đoàn Đức
Feb 12, 2015

In Pascal (sorry but this is the only one I've learned :p)

Input:

Output:

Swapnil Kusumwal
Jan 2, 2015

IN BLUEJ,

class brilliant {

public static void main()
{
    int c=2;
    for (int x=2;x<1000;x++)
    {

        double d=Math.sqrt(x);
        int e=(int)d;
        if (d==e)
        {
            int f=0;
            for (int y=2;y<x+1;y++)
            {
                if ((x+1)%y==0)
                {
                   f=f+1;
                }
            }
            if (f>0)
            {

            }
            else
            {
                c=c+(x+1);
        }
    }
}
System.out.println(c);

} }

Answer ====> c=2271

Prime Sum

The answer is 2271.

7 solutions

0 pending reports