Project Euler

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;
  }
}