Optimize finding GCD of all pairs of divisors

Question

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) {
        string num = Console.ReadLine();
        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");
        Console.Read();
    }

    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.Add(i);
            }
        }
        divisors.Add(a);
        divisors.Reverse();
        return divisors;
    }

Answer 1

• 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.