# Project Euler #10 - sum of primes below two million

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

public class Java {

public static void main(String[] args) {
long start = System.nanoTime();

long sum = 0;

for (int i = 2; i < 2000000; i++) {
boolean isPrime = true;

if ((i % 2 == 0 || i % 3 == 0) && (i!=2 || i!=3 || i!=5)) {
isPrime = false;
} else {
for (int j = 5; j <= Math.sqrt(i); j = j + 6) {
if (i % j == 0 || i % (j + 2) == 0) {
isPrime = false;
break;
}
}
}

if (isPrime == true) {
sum += i;
}
}

System.out.println(sum);
long end = System.nanoTime();
System.out.println(end - start);
}


This is probably not efficient since i am using a lot of if-else statements and conditions.

        if ((i % 2 == 0 || i % 3 == 0) && (i!=2 || i!=3 || i!=5)) {


If i is divisible by 2 or 3, it will never be equal to 5. So you could just say

        if ((i % 2 == 0 || i % 3 == 0) && (i!=2 && i!=3)) {


Note that I changed the || to &&, as the original logic was incorrect. (i!=2 || i!=3) is true for all i. When i is 2, it's not 3, so true. And vice versa.

But we can do better. Rather than saying

    long sum = 0;

for (int i = 2; i < 2000000; i++) {


Say

    // sum 2 and 3 manually
long sum = 5;

// 5 is the first prime after 2 and 3
for (int i = 5; i < 2000000; i++) {


and then you can just say

        if ((i % 2 == 0 || i % 3 == 0)) {


which is much simpler.

Be careful of things like

            for (int j = 5; j <= Math.sqrt(i); j = j + 6) {


This relies on the compiler realizing that Math.sqrt(i) is invariant in regards to the j loop and optimizing it out. If the compiler does not do that, it will do an expensive square root operation on every iteration of the loop. Something like

            for (int j = 5, m = (int) Math.sqrt(i); j <= m; j = j + 6) {


may be more efficient.

Note: I tend to agree that this problem is well suited to a Sieve of Eratosthenes. My suggestions are less for this problem and more for coding in general. If you do use a Sieve as suggested in @FlorianSchaetz's answer consider

        for (int j = i * i; j <= limit; j += i) {
knownNotPrime[j] = true;
}


As all multiples of i less than i * i would have been picked up already.

Note that starting j at i * i rather than i saves calculating both limit / i and i * j at the cost of changing j++ to j += i.

• Thanks for being spot on .... yes... changing the logic was a very valuable idea.... My logic was like spaghetti... :D – Altamash Khan Sep 15 '15 at 9:16

Well, first of all, sorry, but your code is buggy. You are missing 2 and 3, because of this:

if ((i % 2 == 0 || i % 3 == 0)


...since this will be true for 2 and 3. So your result is off by 5.

Also this part is 100% useless:

(i!=2 || i!=3 || i!=5))


How many values for i you can imagine for which this statement is false?

• Let's try i = 1 -> true, because 1 != 2 (i != 2)
• Now we try i = 2 -> true, because 2 != 3 (i != 3)
• Now we try i = 3 -> true, because 3 != 2 (i != 2)
• Last try: i = 5 -> true, because 5 != 2 (i != 2)

So, this statement is always true.

Anyway, another solution (getting more speed by sacrificing memory) would be to not calculate if every number is a prime, but do something like this...

final int limit = 2000 * 1000;

final boolean[] knownNotPrime = new boolean[limit + 1];

long sum = 0;

for (int i = 2; i < limit; i++) {

if (!knownNotPrime[i]) {
sum += i;

for (int j = 2; j <= (limit / i); j++) {
knownNotPrime[j * i] = true;
}
}

}


In other words, for every prime you calculate the multiples (up to the limit) and store them in a boolean array (you could decrease the memory by a factor of 8 by using a bitfield, just didn't want to complicate the whole thing).

Since "being not a multiple of any number lesser than itself" is pretty much the definition of "prime", you already know if a number is a prime when you reach it and it's not marked in the array. And if it isn't, you know that it's a multiple of some lesser prime - and thus, all it's multiples will already be known as non-prime, no need to re-calculate them.

Your code takes around 217ms to run, mine takes 17, but on the other hand, mine takes way more than 12 times the memory, even if you used a bitfield.

Note: After using google and trying to remember what I learned in school, this is probably a variation of the Sieve of Eratosthenes and I have no idea how good this implementation is. Probably there are much better solutions out there, I guess.

• Aah... my bad.... i deliberately tried to remove 2 and 3 and i wanted to add 5 to the result... but forgot to put it in the code – Altamash Khan Sep 15 '15 at 9:11
• As a side note, you can write long numbers like this: 2_000_000. Then you don't need to have a * that means nothing but looks like it might. – Fund Monica's Lawsuit Jan 21 '16 at 1:41
• As long as you are sure that you are using Java 7 or higher, yes. – Florian Schaetz Jan 21 '16 at 7:35