# Project Euler

### A Taste of Number Theory

#### 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])