# Optimize finding GCD of all pairs of divisors

I've come up with a solution for Euler Problem 530, but my code runs too slowly to actually get the answer (solving for 10^15). What can I do to optimize it to run faster?

    static void Main(string[] args) {
double bigtotal = 0;
double n = double.Parse(num);
Dictionary<double, List<double>> divisorDict = new Dictionary<double, List<double>>();
Dictionary<double, double> gcdSums = new Dictionary<double, double>();
for (double i = 1; i <= n; i++) {
List<double> divisors = getDivisors(i);
divisorDict[i] = divisors;
double total = 0;
foreach (double d in divisors) {
double gcd;
if (gcdSums.ContainsKey(d)) {
gcd = gcdSums[d];
} else {
List<double> divA = divisorDict[d];
List<double> divB = divisorDict[i / d];
gcd = GCD(divA, divB);
gcdSums[d] = gcd;
}
total += gcd;
}
//Console.WriteLine("The total is " + total);
bigtotal += total;
if (i % 1000 == 0) { Console.WriteLine(i); }
}
Console.Write("The big total is" + bigtotal + "\n");
}

static double GCD(List<double> divA, List<double> divB) {
foreach (double i in divA) {
foreach (double j in divB) {
if (i == j) {
return i;
}
}
}
Console.WriteLine("Error");
return 0;
}

static List<double> getDivisors(double a) {
List<double> divisors = new List<double>();
for (double i = 1; i <= a/2; i++) {
if ((a / i) % 1 == 0) {
}
}
divisors.Reverse();
return divisors;
}

• Always describe in the question what your code does, even if you got your inspiration on some other site and also linked that (as you should). Oct 27, 2015 at 23:09

• Superficial optimization

• I don't see the reason for using double. $10^{15}$ fits in 50 bits, so 64 bit integers would suffice.

• GCD does a linear search over divB. Consider binary search instead.

• A divisor computation loop runs while $i \le \frac{a}{2}$ (i <= a/2). It should only run while $i^2 \le a$ (i*i <= a).

• Real optimization

The problem asks to compute $F(k)= \sum\limits_{n=1}^k \, \sum\limits_{d|n}\, \text{gcd}(d,\frac n d)$

Swapping the order of summation (that is, outer sum is over divisors d, inner sum is over integers divisible by this divisors, that is, n*d) results in $F(k) = \sum\limits_{d=1}^{d^2 <= k} \, \sum\limits_{n=1}^{dn <=k}\, \text{gcd}(d, n)$.

Notice that this order runs in $O(k \log^2k)$ computations of gcd and avoids factorization whatsoever. It does require computation of gcd which is not an efficiency burden (expected complexity is logarithmic).

You may further optimize it by removing repeated gcd computations and utilizing symmetry between n and d.