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 operations using the Eulerian algorithm.
Prime Testing is performed for:
n = 1; n*n <= (number being tested); n++
To give an idea of how long this code takes to execute:
- It ran F(10)=32 in 0.008 seconds.
- It ran F(1000)=12766 in 0.019 seconds.
- It ran F(100,000)=2907546 in 29.724 seconds.
This was the optimisation suggested in another post on codereview.
It seems to me that the alternative summation suggested there is wrong! F(10)
would give you 22, not 32. I'm not sure how the alternative summation was derived.
double duration = (System.nanoTime()- start)/1000000000;
, and removing the end statement it will be more accurate. \$\endgroup\$