Attemped Sieve of Eratosthenes I've just done Project Euler question 10:


  Find the sum of all the primes below two million.


I get the correct answer and it takes about 3.5-4 seconds to run.

I tried to use the Sieve of Eratosthenes to find the solution, but am not sure if my solution is using the method correctly, or if it could be improved in any way.

I was also wondering if anyone knew if for this case, is the Sieve of Eratosthenes the fastest way?

Any feedback would be very much appreciated.

import java.math.BigInteger;
import java.util.ArrayList;

public class Problem10 {

public static void main (String[] args) {
    double startTime = System.currentTimeMillis();
    run();
    double endTime = System.currentTimeMillis();
    System.out.println("Took "+((endTime - startTime) / 1000)+" seconds"); 
}

public static void run() {
    ArrayList&lt;Boolean&gt; numbers = new ArrayList&lt;Boolean&gt;();
    for (int i = 0; i &lt; 2000000; i++) {
        if (i &lt; 2) numbers.add(false); else numbers.add(true);
    }

    BigInteger count = BigInteger.ZERO;
    int index = 0;
    while (index &lt; 2000000) {
        if (numbers.get(index) == true) { // if the index is true, i.e. prime
                count = count.add(BigInteger.valueOf(index)); // then add it's sum to the count
                for (int i = index; i &lt; numbers.size(); i+=index) { // and then go through all of it's multiples (including itself)
                    if(numbers.get(i) == true) {
                        numbers.set(i, false); // and set them all to be false
                    }
                }
        }
        index++;
    }
    System.out.println("The sum of all primes below 2 million is:  " + count);
}
}
Boolean expressions evaluate to boolean. That means that can be used interchangeably with true and false.

if (numbers.get(index) == true)


is the same as

if (numbers.get(index))




if (i &lt; 2) numbers.add(false); else numbers.add(true);


is the same as 

numbers.add(i&gt;=2);


It is also much easier to read and edit. Collapsing an if/else into one line is bad form. It forces the reader to look carefully at what is actually happening. Where as separate it across multiple lines, as you do with your other if statements allows each part to stand on its own. Additionally, dropping the curly braces means you will need to do extra work if you want to add another statement. Or, if you forget, the second line will execute unconditionally.



Why are you using a while loop for the main body? It does exactly what a for loop is designed to do and your code shows that you understand how to use them.



You should extract 2000000 into a constant. The name will make it clearer what the meaning of the number is. The constant will mean that the value clearly means the same thing in both places.



Comments are best used for describing why something is happening. Code is best for stating what is happening. If you feel that the code is complicated enough that you need to explicitly say  what is happening, that is an indication that extracting that piece of code into a function with a descriptive name would be helpful.