Find the sum of all the primes below two million.

Project Euler Problem 10: The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.
Solution: Here we show a brute force approach to solve this problem. An efficient version of this would problem would be published soon.
In this solution, we keep on finding prime numbers below 2 million and add them using a BigInteger variable.


Java Program to Generate next prime number.


package evaluator;
public class FindPrime {
/*
* Finds the next prime given a number.
* It does NOT checks if the number itself is a prime.
* It finds the next prime number after the given number.
*/
public long nextPrime(long num){
num = num + 1;
boolean flag = false;
// Primes only after 10
if(num > 10){
for(;;){
flag = true;
if(num % 2 == 0){
num = num + 1;
continue;
}
if(num % 3 == 0){
num = num + 1;
continue;
}
long r = (int) (Math.sqrt(num));
// We know that no is not divisible by 2,3.
long f = 5;
while(f<=r){
if(num % f == 0){
num = num +1;
flag = false;
break;
}
if(num % (f+2) == 0){
num = num +1;
flag = false;
break;
}
f = f + 6;
flag = true;
}
if(flag){
return num;
}
}
}
// Primes if no. less than 10
num = num - 1;
if(num == 0 || num == 1) return 2;
if(num == 2) return 3;
if(num < 5 && num >= 3) return 5;
if(num < 7 && num >= 5) return 7;
if(num < 10 && num >= 7) return 11;
// Hope this is not reached ever
return 0;
}
}

Java Program to Add all prime numbers.


package evaluator;
import java.math.BigInteger;
public class FindSum implements Runnable{
public BigInteger findSumOfPrimes(long start, long end){
FindPrime prime = new FindPrime();
BigInteger primeNum = new BigInteger("0");
BigInteger sumOfPrimes = new BigInteger("0");
while(start<end){
start = prime.nextPrime(primeNum.longValue());
primeNum = BigInteger.valueOf(start);
sumOfPrimes = sumOfPrimes.add(primeNum);
System.out.println("Adding prime number : "+ primeNum);
System.out.println("Sum of nums : "+ sumOfPrimes);
}
if(primeNum.compareTo(BigInteger.valueOf(2000000)) > 0){
sumOfPrimes = sumOfPrimes.subtract(primeNum);
}
return sumOfPrimes;
}
@Override
public void run() {
}
}

Java Program to Display sum of all prime numbers.


package display;
import java.math.BigInteger;
import evaluator.FindSum;
public class DisplayResult {
public static void main(String [] args){
long startTime = System.currentTimeMillis();
BigInteger result = new BigInteger("0");
BigInteger temp = new BigInteger("0");
FindSum find = new FindSum();
result = find.findSumOfPrimes(0, 2000000);
System.out.println("Sum of primes: " + result);
}
}

This program is using brute force approach to calculate the sum of primes. So, it takes about an hour to calculate the sum.
Keeping this as one of the possible solution we will device a way to find the solution in an efficient manner soon.

Leave a Reply

Your email address will not be published. Required fields are marked *