c - 1000 以下的所有 3 或 5 的倍数之和在 C 中给出错误答案

Question

欧拉计划问题:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

我的 C 代码:

long int x;

long int y;

long int z = 0;

long int a = 0;

long int b = 0;
   
for(x= 0; x < 1000; x += 3)  
    a = a + x;
   
for(y = 0; y < 1000; y += 5)  
    b = b + y;
   
z = a + b;
printf("%lu", z);
   
return 0;

但我得到的输出是 266333，这是错误的。我用 Python 检查了答案，我答对了。我想知道我对 C 代码做错了什么。正确答案是 233168

我的 Python 代码:

print(sum(x for x in range(1000) if x % 3 == 0 or x % 5 == 0))

Answer 1

有些数字可以同时被 3 和 5 整除，你不应该将它们相加两次。像这样的代码将给出正确的结果:

long int x,total = 0;

for(x = 0; x < 1000; ++x)
{
    if(x % 3 == 0)
        total = total + x;
    else if(x % 5 == 0)
        total = total + x;
}

printf("%ld", total);

在上面的代码中，if else if 确保一个数字是否可以被 3 或 5 整除。并允许在此基础上求和。

它可以进一步优化为:

for(x= 0; x < 1000; ++x)
{
    if(x%3 == 0 || x%5 == 0)
        total = total + x;
}

Above solution is O(n) for better time complexity O(1) we can use Arithmetic Progression with interval of 3 and 5.

n = 给定范围 (1...R) 中给定数字 (Num) 的倍数总数。在这种情况下 (1...1000)

a1 = 第一个倍数。此处为 3 或 5。

an = 最后倍数。即 3Xn

因此，以下代码将计算给定范围 1...lastOfRange(不包括 lastOfRange)的序列总和，间隔为 3/5 (Num)。

long SumOfSeries(long Num, long lastOfRange)
{
    long multiplesCount = (lastOfRange-1) / Num; //(lastOfRange-1) to exlude the last number 1000 here
    long result = multiplesCount * (Num + (multiplesCount * Num)) / 2;//Num = a1, (multiplesCount * Num) = an.
    return result;
}

这可以称为:

long N = 1000;
Sum = SumOfSeries(3, N) + SumOfSeries(5, N) - SumOfSeries(3*5, N);
printf("%ld", total);