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 &lt; 2000000; i++) {
        if (isPrime(i)) {
            sum += i;
        }
    }
    return sum;
}
/*
 * The sequence of triangle numbers is generated by adding the natural
 * numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 =
 * 28. The first ten terms would be:
 * 
 * 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
 * 
 * Let us list the factors of the first seven triangle numbers:
 * 
 * 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28:
 * 1,2,4,7,14,28 We can see that 28 is the first triangle number to have
 * over five divisors.
 * 
 * What is the value of the first triangle number to have over five hundred
 * divisors?
 * http://projecteuler.net/problem=12
 */ 
public static long get12() {
    for (int i = 1;; i++) {
        long n_t = Sumk(i);
        int d = getDivisorCount(n_t);
        if (d &gt;= 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 &lt;= 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 &lt;= 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 &lt; 2000000; i++) {


Right, but

long sum = 1;// 2 is also a prime
for (int i = 3; i &lt; 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 &lt;= n; i += 2)
        if (n % i == 0)
            return false;
    return true;
}


That's fine. Just note that (i &amp; 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 &lt;= 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 &lt;= n;) {


Here, you could use a test like i * i &lt; n again, couldn't you?

        if (isPrime(i)) {


My above point was about efficiency. Actually, in order for the below computation (d *= (d2 + 1)) to work, it's necessary to use only primes here. However,


when you get a divisor of the (reduced) n here
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 &gt;&gt;= d2;


&nbsp;

    }
    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 &gt;&gt;= d2;
    }
    for (int i=3; i*i &lt;= 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).