Project Euler Problem 530: sum of sum of greatest common divisors

Here is a description of Project Euler problem 530:


Every divisor \$d\$ of a number \$n\$ has a complementary divisor \$n/d\$.


Let \$f(n)\$ be the sum of the greatest common divisor of \$d\$ and \$n/d\$ over all positive divisors \$d\$ of \$n\$, that is \$\displaystyle f(n)=\sum_{d/n}\gcd\left(d, \frac{n}{d}\right)\$.


Let \$F\$ be the summatory function of \$f\$, that is \$\displaystyle F(k) = \sum_{n=1}^{k}f(n)\$.


You are given that \$F(10)=32\$ and \$F(1000)=12776\$.


Find \$F(10^{15})\$.

My solution for Euler Problem 530 is as follows:

import java.math.BigInteger;

public class problem530 {

public static void main(String[] args) {

    double start = System.nanoTime();

    BigInteger result = BigInteger.ZERO;
    BigInteger one = BigInteger.ONE;

    for (long i = 1; i <= 1000; i++){
            if ( i == 1) {
                result = result.add(one);
            }
            if (PrimeTest.testLong(i) == true) {
                result = result.add(one).add(one);
            }
            else if (i != 1 && PrimeTest.testLong(i) == false) {
                result = result.add(one);
                for(long j = 1; j*2 <= i; j++) {
                    if (i%j == 0) {
                    long sub = i / j;
                    result = result.add(BigInteger.valueOf(GCD(sub, j)));
                }
            }
        }
    }

    System.out.println(result);

    double duration = (System.nanoTime() - start)/1000000000;

    System.out.println("Your code took " + duration + " seconds to execute.");

}
}

I have PrimeTest and GCD written in libraries. The code works (it returns the correct answer for the test cases). It takes unimaginably long to get the answer for \$F(10^{15})\$ though (essentially, I won't get the answer). I'm looking for ways to optimise it.

At this link, @alan wrote something there about a sieve (presumably in C++?) which I don't quite understand. Does anyone have any ideas for optimisation?

• I perform GCD

Special Cases and Branching

If you look at your prime checking, your code is:

if (prime(i) == true) {
    // ...
}
else if (prime(i) == false) {
    // ...
}

This ends up with you checking composite numbers for primality twice! Once in each branch! The second part could have just been else. Additionally, explicitly checking for == true is an anti-pattern. Prefer:

if (prime(i)) {
    // ...
} else {
    // ...
}

That said, why is being prime a special case? Your non-prime logic would've worked just fine on primes too! And for 1! So just drop all the branches completely and simply iterate.

Need a better algorithm

10^15 is simply too big to brute force the answer. Even dropping all the unnecessary extra work you're doing is likely insufficient. You'll have to try to come up with some optimal substructure this problem has so that you can use dynamic programming.

StackExchange Code Review Q#114935, answer score: 4