5
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$
        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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ Thanks for being spot on .... yes... changing the logic was a very valuable idea.... My logic was like spaghetti... :D \$\endgroup\$ – Altamash Khan Sep 15 '15 at 9:16
4
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Altamash Khan Sep 15 '15 at 9:11
  • \$\begingroup\$ 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. \$\endgroup\$ – Fund Monica's Lawsuit Jan 21 '16 at 1:41
  • \$\begingroup\$ As long as you are sure that you are using Java 7 or higher, yes. \$\endgroup\$ – Florian Schaetz Jan 21 '16 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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