所有3或5的倍数的总和低于1000在C中给出了错误的答案

Question

项目欧拉问题:

如果我们列出下面所有的自然数,10那就是3 or 5我们得到的3, 5, 6 and 9.这些倍数的总和是23.

找到3 or 5下面所有倍数的总和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;
}

以上解决方案是O(n)以获得更好的时间复杂度O(1)我们可以使用间隔为3和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);

Answer 2

答案可以通过简单的算术计算,无需任何迭代.许多Project Euler问题旨在让您考虑找到解决方案的聪明方法,而不仅仅是使用计算机的原始功能来进行计算.

给定正整数N和F,小于N的F的正倍数的数量是floor((N -1)/ F).(floor(x)是不大于x的最大整数.)例如,5的小于1000的倍数是floor(999/5)= floor(199.8)= 199.

令n为该倍数,floor((N -1)/ F).

第一个倍数是F,最后一个倍数是n • F.例如,对于1000和5,第一个倍数是5,最后一个倍数是199•5 = 995.

倍数是均匀间隔的,因此它们的平均值等于第一个和最后一个的平均值,因此它是(F +*n**F*)/ 2.

乘数的总和等于它们的平均值乘以它们的数量,因此F的倍数小于N的总和是n •(F + n • F)/ 2.

正如我们在其他答案和评论中看到的那样,将3的倍数和5的倍数之和加起来计算两次3和5的倍数.我们可以通过减去这些数字的总和来纠正这个问题.3和5之和的倍数是15的倍数.

因此,我们可以使用简单的算法计算所请求的和,而无需任何迭代:

#include <stdio.h>


static long SumOfMultiples(long N, long F)
{
    long NumberOfMultiples = (N-1) / F;
    long FirstMultiple = F;
    long LastMultiple = NumberOfMultiples * F;

    return NumberOfMultiples * (FirstMultiple + LastMultiple) / 2;
}


int main(void)
{
    long N = 1000;
    long Sum = SumOfMultiples(N, 3) + SumOfMultiples(N, 5) - SumOfMultiples(N, 3*5);

    printf("%ld\n", Sum);
}

当您执行其他项目Euler问题时,您应该寻找类似的想法.