#### Problem 10: Summation of Primes

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

#### The Catch

How to efficiently generate a list of prime below a given upper bound.

#### The Light

Including the first prime number, 2, in a sum variable, we can loop from 3 to 2,000,000 and reuse the prime checking code in Problem 3 and increment for every odd number. The sum will probably get too large for a type `int`

variable to hold, causing a number overflow error. Use a type `long`

variable to solve this issue. This approach, however, requires approximately 1,000,000 iterations and takes as long as half a second to execute, which is not very efficient.

The Sieve of Eratosthenes discussed in Problem 35 will yield a much better result.

#### The Code

import java.util.*; public class Problem10 { public static void main(String[] args) { long sum = 0; List primeList = generatePrimes(2000000); for(int i = 0; i < primeList.size(); i++) { sum += primeList.get(i); } System.out.println(sum); } public static List generatePrimes(int max) { boolean[] isComposite = new boolean[max + 1]; for (int i = 2; i * i <= max; i++) { if (!isComposite [i]) for (int j = i; i * j <= max; j++) { isComposite [i*j] = true; } } ArrayList list = new ArrayList(); for (int i = 2; i <= max; i++) { if (!isComposite [i]) list.add(new Integer(i)); } return list; } }