2
\$\begingroup\$

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<Boolean> numbers = new ArrayList<Boolean>();
    for (int i = 0; i < 2000000; i++) {
        if (i < 2) numbers.add(false); else numbers.add(true);
    }

    BigInteger count = BigInteger.ZERO;
    int index = 0;
    while (index < 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 < 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);
}
}
\$\endgroup\$
0

2 Answers 2

2
\$\begingroup\$

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 < 2) numbers.add(false); else numbers.add(true);

is the same as

numbers.add(i>=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.

\$\endgroup\$
2
  • \$\begingroup\$ Thank you very much for your reply :). I've implemented the suggestions you made and thank you for them. Do you know if there is a better algorithm to use for this question, or if there are any major improvements I could make? Thank you again. \$\endgroup\$ Commented Dec 23, 2014 at 19:24
  • \$\begingroup\$ I didn't spend any time looking at the algorithm, but did find this page that talks about the problem and optimizations that can be used. \$\endgroup\$ Commented Dec 23, 2014 at 19:35
1
\$\begingroup\$

I can't see much I would do differently with the algorithm, so I can only suggest a few minor things

for (int i = 0; i < 2000000; i++) {
    if (i < 2) numbers.add(false); else numbers.add(true);
}

This if/else can be slightly hardcoded as

numbers.add(false); //0
numbers.add(false); //1
for (int i = 2; i < 2000000; i++) {
    numbers.add(true);
}

But I do prefer @unholysampler's way of doing it as it is much more flexible.


You don't necessarily need BigInt for this problem, long would suffice until you are asked to sum primes to over 4 billion, and that's being pessimistic (presuming every number is prime)


for (int i = index; i < 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
    }
}

You don't really need the if statement, you can just set it to false, I doubt it will have much impact on performance including it or not

also a very small thing, since you never actually go backwards you can just start from index*index. For example if the index was at 3, you can start from 9 as you never go back to 3, and 6 would be marked off from the multiples of 2


In terms of better algorithms I would suggest looking at the sieve of atkins, or if that is a bit too much at the moment, look at what you are incrementing by, and see if you can make any improvement there

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.