Problem 10: Summation of primes

*Difficulty: Easy

Problem:

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

Find the sum of all the primes below two million.

How to solve:

As problem 7, we have at least two ways to solve this problem.

  • 1 :  Using sieve Eratosthenes to create a dictionary of prime numbers that are smaller than 2,000,000. Then, go through the dictionary and sum up all the prime numbers.
  • 2:  Using a helping function to determine if a number is prime or not. The speed and run time of this method heavily depend on how you construct the helping function. Here I’m using naive primality test. You can reference pseudo code on Wiki .

About the run time, the first method takes about from 30 to 60 ms , mean while, the second method takes about 250 to 340 ms

Implementation: Java

import java.util.Arrays;

public class Prob10 {

private static boolean[] sieveEratosthenes;

private static final intSIZE = 2000000;

public static void main(String[] args) {

long cur = System.currentTimeMillis();

sieveEratosthenes= new boolean[SIZE];

Arrays.fill(sieveEratosthenes, true);

for(int i = 2; i <= (int)Math.sqrt(sieveEratosthenes.length); ++i) {

if(sieveEratosthenes[i])

for(int j = i*2; j < sieveEratosthenes.length; j+=i)

sieveEratosthenes[j] = false;

}

long sum = 0;

for(int i = 2; i < sieveEratosthenes.length; ++i)

if(sieveEratosthenes[i])

sum += i;

System.out.println(sum);

System.out.println(“Took “ + (System.currentTimeMillis() cur) + ” ms”);

/*

long sum = 0;

for(int i = 2; i < SIZE; ++i) {

if(isPrime(i))

sum +=i;

}

System.out.println(sum);

System.out.println(“Took ” + (System.currentTimeMillis()-cur) + ” ms“);

*/

}

private static boolean isPrime(int n) {

if(n <= 1) return false;

else if(n <= 3)

return true;

else if(n % 2 == 0 || n % 3 == 0)

return false;

int i = 5;

while(i*i <= n) {

if(n%i == 0 || n%(i+2) == 0)

return false;

i += 6;

}

return true;

}

}

Advertisements