Euler退职计划

Question

现在我正在做Euler 1项目：

如果我们列出所有低于10的自然数，它们是3或5的倍数，我们得到3，5，6和9。这些倍数之和是23。找出低于1000的3或5倍数之和。

这是我的代码，在0毫秒内运行：

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    int sumNums = 0;

    for(int i = 0; i < 1000; i++)
    {
        if (i % 3 == 0 || i % 5 == 0) { sumNums += i; }
    }

    s.Stop();

    Console.WriteLine(sumNums);
    Console.WriteLine(s.ElapsedMilliseconds);
}

我也有这个版本，它也在0毫秒内运行。实际上，在同一个计时器中运行这两个方法会导致0毫秒的结果：

static void Main(string[] args)
{
    Stopwatch s = new Stopwatch();
    s.Start();

    int sumNums = 0;

    for (int i = 0; i < 1000; i += 3)
    {
        sumNums += i;
    }

    for (int i = 0; i < 1000; i += 5)
    {
        sumNums += i % 3 == 0 ? 0 : i;
    }

    s.Stop();

    Console.WriteLine(sumNums);
    Console.WriteLine(s.ElapsedMilliseconds);
}

什么可以改进，哪个版本更好？

Answer 1

我没有C#编译器，但我认为如果您将i % 3放在第二个循环中，让它将所有倍数之和为5，然后再进行一次传递以删除15的倍数，那么第二个版本会更快。由于3、5、15的求和是重复的，所以我会引入一个助手函数，如下所示：

static int sumOfMultiples(int x, int limit)
{
    int sum = 0;
    for (int i = x; i < limit; i += x)
    {
        sum += i;
    }
    return sum;
}

然后在Main中，您可以写：

int max = 1000;
int sumNums = sumOfMultiples(3, max) + sumOfMultiples(5, max) - sumOfMultiples(15, max);

当然，@VikasGupta在评论中的建议是最好的，使用纯数学而不是循环，将助手重写为：

static int sumOfMultiples(int x, int limit)
{
    int n = (limit - 1) / x;
    return x * n * (n + 1) / 2;
}

Answer 2

由于我没有C#编译器(对不起)，所以我将这两个程序转换为Java以进行测试。

第一代码：

平均速度: 80000- 90000纳秒

评论：

for(int i = 0; i < 1000; i++)
{
    if (i % 3 == 0 || i % 5 == 0) { sumNums += i; }
}

您可以在不影响结果的情况下安全地启动3：

for(int i = 3; i < 1000; i++)
{
    if (i % 3 == 0 || i % 5 == 0) { sumNums += i; }
}

此外，您应该将if语句分成三行，以获得更好的可读性：

for(int i = 3; i < 1000; i++)
{
    if (i % 3 == 0 || i % 5 == 0) {
        sumNums += i;
    }
}

这个大概就是这个了。

第二代码：

平均速度: 60000 - 65000纳秒

评论：

for (int i = 0; i < 1000; i += 3)
{
    sumNums += i;
}

for (int i = 0; i < 1000; i += 5)
{
    sumNums += i % 3 == 0 ? 0 : i;
}

与以前一样，您可以从稍微大一点的数字开始：

for (int i = 3; i < 1000; i += 3)
{
    sumNums += i;
}

for (int i = 5; i < 1000; i += 5)
{
    sumNums += i % 3 == 0 ? 0 : i;
}

Thoughts

我认为两者在1000的时候都是相等的，但随着数字的增加，第一个数字会明显减慢。