Project Euler #10 and #12 in Java - Prime Numbers

I am dealing with a huge time taking with primes. I hope you know they are pretty random and that's why create many problem. Both are using the same logic/methods.

/*
 * The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17. Find the sum of all
 * the primes below two million.
 * http://projecteuler.net/problem=10
 */

public static long get10() {
    long sum = 0;// 2 is also a prime
    for (int i = 2; i = 500) {
            return n_t;
        }
    }
}
public static long Sumk(int n) {
    // Sum of k from 1 to n =n*(n+1)/2 [Also n'th triangular number]
    return n * (n + 1) / 2;
}
public static boolean isPrime(int n) {
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0)
            return false;
    return true;
}

public static int getDivisorCount(long n) {
    int d = 1;
    for (int i = 2; i <= n;) {
        if (isPrime(i)) {
            int d2 = 0;
            while (n % i == 0) {
                ++d2;
                n /= i;
            }               
            d *= (d2 + 1);
        }
        if (i == 2) {
            ++i;
        } else {
            i += 2;
        }
    }
    return d;
}

Currently the output is:

10


Time taken 4.160109858 seconds

12


Time taken 6.856344169 seconds

You could make use of the Sieve of Eratosthenes, which would give you all the speed you need. There's a lot of such code here on CR, so let's gop to the review.

long sum = 0;// 2 is also a prime
for (int i = 2; i < 2000000; i++) {

Right, but

long sum = 1;// 2 is also a prime
for (int i = 3; i < 2000000; i+=2) {

does the job as well. No big improvement as the evens get tested very fast.

long n_t = Sumk(i);

This is a terrible name, but maybe OK in math code.

int d = getDivisorCount(n_t);

What do we know about divisors of a product? Right, you could simply "add" them.1 No advantage here, but a big speed up for big numbers (coming in later Euler problems).

As you count the divisors of a (a+1) and then (a+1) (a+2), you could reuse the divisors for (a+1) for a speedup factor of 2.

public static long Sumk(int n) {

Method names always start with lowercase.

public static boolean isPrime(int n) {
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    for (int i = 3; i * i <= n; i += 2)
        if (n % i == 0)
            return false;
    return true;
}

That's fine. Just note that (i & 1) is a faster way of computing i % 2 for non-negative i.

public static int getDivisorCount(long n) {
    int d = 1;
    for (int i = 2; i <= n;) {
        if (isPrime(i)) {

And that's the culprit! You're doing an expensive operation (isPrime) in order to save a much cheaper one (division)!

Actually, the whole method is confusing, so let's go through:

public static int getDivisorCount(long n) {
    int d = 1;

But d is not a nice name. I'd suggest to call it simply result.

for (int i = 2; i <= n;) {

Here, you could use a test like i * i

• it's always the least divisor

-
and the least multiple is always a prime

int d2 = 0;
        while (n % i == 0) {
            ++d2;
            n /= i;
        }               
        d *= (d2 + 1);
    }
    if (i == 2) {
        ++i;
    } else {
        i += 2;
    }

That's OK, but I'd handle 2 specially. There's a nice trick (irrelevant here) for getting out all powers of two:

int d2 = Integer.numberOfTrailingZeros(n);
n >>= d2;

 

}
    return d;
}

OK. Btw., my solutions to these problems take nearly one second. That's not fast, but I don't care as there's enough to optimize when working on the harder problems.

My divisorCount

It takes 0.12 seconds and could surely be improved via memoization or a precomputed list of primes (a list up to Math.sqrt(Integer.MAX_VALUE) can be easily found in internet).

private int divisorCount(int x) {
    int result = 1;
    {
        final int d2 = Integer.numberOfTrailingZeros(x);
        result *= d2 + 1;
        x >>= d2;
    }
    for (int i=3; i*i <= x; i+=2) {
        int d2 = 0;
        while (x%i == 0) {
            ++d2;
            x /= i;
        }
        result *= d2 + 1;
    }
    if (x!=1) result *= 2;
    return result;
}

1 I was wrong here. The prime factors list (multiset) can simply be concatenated. The number of divisors can be computed easily using them. Let's say that this is what I meant by "add" (it's not, I was plain wrong, but don't tell it further).

StackExchange Code Review Q#91812, answer score: 4