可能在我的代码中优化？

Question

为了解决欧拉项目问题5,我编写了以下程序:

class p5
{
    const int maxNumber = 20;
    static void Main(string[] args)
    {
        Job(); // First warm-up call to avoid Jit latency

        var sw = Stopwatch.StartNew();
        var result = Job();
        sw.Stop();

        Debug.Assert(result == 232792560);
        Console.WriteLine(result);
        Console.WriteLine(sw.Elapsed);
        Console.ReadLine();
    }

    private static int Job()
    {
        var result = Enumerable.Range(1, int.MaxValue - 1)
            .Where(
                n => Enumerable.Range(maxNumber / 2 + 1, maxNumber / 2).All(c => n % c == 0)
            ).First();
        return result;
    }
}

但是,我发现它有点长(17秒,处于释放模式),即使它正在工作.

有没有可能的优化？

仅供参考,我尝试了AsParallel方法,但正如预期的那样,大量的工作太小而且上下文切换比利益更重(超过1分钟):

    var result = Enumerable.Range(1, int.MaxValue - 1).AsParallel()
        .Where(
            n => Enumerable.Range(maxNumber / 2 + 1, maxNumber / 2).All(c => n % c == 0)
        ).First();
    return result;

[编辑]根据马丁的建议,这个版本除以10所花费的时间:

    private static int Job()
    {
        var n =2;
        bool result;
        do
        {
            result = true;
            for (int c = maxNumber / 2; c <= maxNumber; c++)
            {
                if (n % c > 0)
                {
                    result = false;
                    break;
                }
            }
            n ++;//= 2;
        } while (!result);
        return n;
    }

[编辑]总结我所有的测试,粗略的执行时间:

• 我的第一次实施:20秒
• 删除了内部enumerable.Range调用(替换为简单的for循环):3秒
• 删除了外部和内部的enumerable.Range调用:1.5秒
• 只取偶数:(只有循环,没有enumerable.range):小于1秒
• 使用drhirsch建议的Gcd/LCm欧几里德算法:0.004 ms

最新的建议显然是个好答案.我感谢drhirsch提出了另一种方法,而不仅仅是简单的循环优化

Answer 1

一个好的优化是使用更好的算法.

这要求数字1..20的最小公倍数,可以通过找到lcm(1,2),然后lcm(lcm(1,2),3)等直到20 来连续计算.

找到lcm的简单算法是将两个数的乘积除以最大公约数.该GCD可以通过熟知的发现euklidian算法在很短的时间.

#include <iostream>

long gcd(long a, long b) {
    if (!b) return a;
    return gcd(b, a-b*(a/b));
}

long lcm(long a, long b) {
    return (a*b)/gcd(a, b);
}

int main(int argc, char** argv) {
    long x = 1;
    for (long i=2; i<20; ++i) 
        x = lcm(x, i);
    std::cout << x << std::endl;
}

这会立即吐出解决方案.