-1
\$\begingroup\$

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;
    }
\$\endgroup\$
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Deduplicator Oct 27 '15 at 23:09
3
\$\begingroup\$
  • 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.