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.

Answer 2

for(int i = currentPrimeIndex ; i < primeNumbers.size() ; i++){
    int multiplier = primeNumbers.get(i);
    toBeRemoved.add(currentPrime * multiplier);
}

At the first step, this generates an ArrayList of 2 million multiples of 2 (toBeRemoved).

Then it iterates over toBeRemoved, scanning the entire array of 2 million candidate primes once for each entry in toBeRemoved. Half the values in toBeRemoved can't possibly be in primeNumbers because they're too big. Each removal results in every value with a greater index than the one removed, being shifted down one place.

I think this is the major source of inefficiency. The usual way to implement the sieve of Eratosthenes is to create an array of 2 million boolean values, initially all true. When i is determined to be non-prime, set possibly_prime[i] to false. To find the next prime, scan forward looking for a true value. To get a list of all primes at the end, iterate the array recording the index of each true value. You should do pretty much the same for the sieve of Euler.

You won't need to optimize beyond that for primes up to 2 million.

Answer 3

To give an answer to the question in this topic title: this is what the project Euler web site says: http://projecteuler.net/index.php?section=about

I've written my program but should it take days to get to the answer? Absolutely not! Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

;-)

Answer 4

Some obvious mistakes:

while(currentPrime <= Math.sqrt(upperLimit))

Square root is calculated in every step (unless optimized by the compiler). You should calculate it once and store the result.

currentPrimeIndex++;

You should at least make the obvious optimization and only test odd numbers. You already know that even numbers aren't primes. This should cut your time in half.

Also, you are using a brute force method to find the prime numbers. This will be slow for large upper limits. You should use a better algorithm for your search - you will be able to find more info in the web, However I don't know if this is allowed in the spirit of Project Euler.

Answer 5

Here is a solution using a simple Sieve of Eratosthenes:

function sumPrimes(n)
    sum, sieve := 0, makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            sum := sum + p
            for i from p*p to n step p
                sieve[i] := False
    return sum

I code this solution in Python here, where it takes one-and-a-quarter seconds. If you're interested in programming with prime numbers, I modestly recommend this essay at my blog.

Answer 6

while(currentPrime <= Math.sqrt(upperLimit)) // It reduces the complexity and one more point the sum is not int. overflow occurs

If it helps you you look at my solution. Here is my solution

public static boolean isPrime(int i) { // general isPrime method
      if (i < 2) {
         return false;
      } else if (i % 2 == 0 && i != 2) {
          return false;
      } else {
           for (int j = 3; j <= Math.sqrt(i); j = j + 2) {
               if (i % j == 0) {
                  return false;
                }
           }
      }

  return true;
 }

    public static boolean isPrimeForOdd(int i){ // only for odds
        for (int j = 3; j <= Math.sqrt(i); j = j + 2) {
             if (i % j == 0) {
                return false;
              }
        }

      return true;
     }

 public static long sumOfPrimes(int n) {
    long sum = 2;

    for (int i = 3; i < n; i += 2) {
          if (isPrimeForOdd(i)) {
              sum += i;
          }
    }

    return sum;
 }

 public static void main(String[] args) throws ParseException {
      System.out.println(sumOfPrimes(2000000));
 }

Answer 7

1. Is list the correct type for this? A Set would perform much better during remove(obj). In your case, try a BitSet.

2. You first create a (long) list of elements to remove and then remove them individually. Why not simply remove them?

3. The result doesn't fit in an int.

Answer 8

import java.util.*;

public class PrimeSum
{
    public static int isPrime(int num)
    {
        int sum = 0;
        int factor = 1;
        while(factor <= num)
        {
            if(num % factor != 0)
            {
                sum += factor;
                factor ++;
            }
            else
            {
                factor ++;
            }
        }
        return sum;
    }

    public static void main(String[] args)
    {
        System.out.println("The program gets the sum of all prime numbers.");

        Scanner scan = new Scanner(System.in);

        System.out.print("Enter a number: ");
        int num = scan.nextInt();

        int sum = isPrime(num);

        System.out.println(sum);
    }
}

Answer 9

Even without sieve, this question is solvable in less than 1 sec complexity. To check whether a number is prime or not : http://www.parseexception.com/how-to-check-whether-a-number-is-prime-or-not/

Perform this operation for all numbers and sum them.