How much time should it take to find the sum of all prime numbers less than 2 million?

Question

I was trying to solve this Project Euler Question. I implemented the sieve of euler as a helper class in java. It works pretty well for the small numbers. But when I input 2 million as the limit it doesn't return the answer. I use Netbeans IDE. I waited for a lot many hours once, but it still didn't print the answer. When I stopped running the code, it gave the following result

Java Result: 2147483647
BUILD SUCCESSFUL (total time: 2,097 minutes 43 seconds)

This answer is incorrect. Even after waiting for so much time, this isn't correct. While the same code returns correct answers for smaller limits.

Sieve of euler has a very simple algo given at the botton of this page.

My implementation is this:

package support;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author admin
 */
public class SieveOfEuler {
    int upperLimit;
    List<Integer> primeNumbers;

    public SieveOfEuler(int upperLimit){
        this.upperLimit = upperLimit;
        primeNumbers = new ArrayList<Integer>();
        for(int i = 2 ; i <= upperLimit ; i++)
            primeNumbers.add(i);
        generatePrimes();
    }

    private void generatePrimes(){
        int currentPrimeIndex = 0;
        int currentPrime = 2;
        while(currentPrime <= Math.sqrt(upperLimit)){
            ArrayList<Integer> toBeRemoved = new ArrayList<Integer>();
            for(int i = currentPrimeIndex ; i < primeNumbers.size() ; i++){
                int multiplier = primeNumbers.get(i);
                toBeRemoved.add(currentPrime * multiplier);
            }

            for(Integer i : toBeRemoved){
                primeNumbers.remove(i);
            }

            currentPrimeIndex++;
            currentPrime = primeNumbers.get(currentPrimeIndex);
        }
    }

    public List getPrimes(){
        return primeNumbers;
    }

    public void displayPrimes(){
        for(double i : primeNumbers)
            System.out.println(i);
    }
}

I am perplexed! My questions is

1) Why is it taking so much time? Is there something wrong in what I am doing?

Please suggest ways for improving my coding style, if you find something wrong.

Question Updated:

Here is the code, where I calculate the sum of the the calculated prime numbers:

package projecteuler;

import java.io.IOException;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.logging.Level;
import java.util.logging.Logger;
import support.SieveOfEuler;

/**
 *
 * @author admin
 */
public class Problem10 {
    private int upperLimit;
    private BigInteger sumOfPrimes;
    public void getInput() {
        try {
            System.out.println("Enter the upper limit");
            upperLimit = Integer.parseInt(br.readLine());
        } catch (IOException ex) {
            Logger.getLogger(Problem10.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    public void execute() {
        BigInteger sum = new BigInteger("0");
        SieveOfEuler soe = new SieveOfEuler(upperLimit);
        ArrayList<Integer> primeNumbers = (ArrayList<Integer>)soe.getPrimes();
        for(int i : primeNumbers){
            sum = sum.add(new BigInteger(Integer.toString(i))) ;
        }
        System.out.println(sum);
    }

    public void printOutput() {
       //System.out.println(sumOfPrimes);
    } 
}

Answer 1

The reason that your Sieve is so slow is that you have made a fundamental mistake. The primeNumbers should be an array of booleans, not a List. When you are finished, the value of primeMumbers[i] will be true for prime numbers and false for composites.

Here's why it makes such a big difference:

• Setting or clearing a flag in array is O(1) ; i.e. a small constant time per operation.
• Removing an element from an ArrayList is O(N) where N is the size of the list ... and very large.
• Each ArrayList.remove(...) operation has to search the list. If the value is no longer there (because you've already removed it), the remove operation has to look at every remaining element in the list ... up to ~2 million of them ... each time it is called.
• When ArrayList.remove(...) finds an element, it removes it by copying all remaining elements after the element one index to the left in the backing array. Again, you are copying up to ~2 million entries ... each time you remove one.

I'd expect a well implemented Sieve of Erasothenes to be able to calculate all prime numbers less than 2 million in a few seconds.