给定一个范围，求能被 3 或 5 整除的数字之和

Question

下面的代码对于较小的数字来说工作得很好，但是对于更大的数字的时间膨胀给了我建议

#include<stdio.h>
int main()
{
  int num;
  int sum=0;
  scanf("%d",&num);
  for(int i=1;i<=num;i++)
  {
    if(i%3==0 || i%5==0)
    sum += i;
  }
  printf("%d",sum);
}
 

为此需要有效的代码

尝试减少代码花费的时间。

Answer 1

答案可以通过简单的算术计算出来，无需任何迭代。欧拉计划的许多问题旨在让您思考找到解决方案的巧妙方法，而不仅仅是使用计算机的原始能力来进行计算。（这是欧拉计划问题 1，除了欧拉计划问题指定使用小于而不是小于或等于的限制。）

\n

给定正整数N和F ，小于或等于N的F正倍数的个数为 \xe2\x8c\x8a N / F \xe2\x8c\x8b。（\xe2\x8c\x8a x \xe2\x8c\x8b 是不大于x 的最大整数。）例如，小于或等于 999 的 5 的倍数为 \xe2\x8c\x8a999/5\xe2 \x8c\x8b = \xe2\x8c\x8a199.8\xe2\x8c\x8b = 199。

\n

令n为该倍数 \xe2\x8c\x8a N / F \xe2\x8c\x8b。

\n

第一个倍数是F，最后一个倍数是n \xe2\x80\xa2 F。例如，对于 1000 和 5，第一个倍数是 5，最后一个倍数是 200\xe2\x80\xa25 = 1000。

\n

倍数间隔均匀，因此所有倍数的平均值等于第一个和最后一个的平均值，因此为 ( F + n F )/2。

\n

倍数的总和等于它们的平均值乘以它们的数量，因此F小于N的倍数的总和为n \xe2\x80\xa2 ( F + n \xe2\x80\xa2 F )/2。

\n

3的倍数和与5的倍数和相加包括3和5的倍数的两倍。我们可以通过减去这些数字的总和来纠正这一点。3和5的倍数都是15的倍数。

\n

因此，我们可以使用简单的算术来计算请求的总和，而无需任何迭代：

\n

#include <stdio.h>\n\n\nstatic long SumOfMultiples(long N, long F)\n{\n    long NumberOfMultiples = N / F;\n    long FirstMultiple = F;\n    long LastMultiple = NumberOfMultiples * F;\n\n    return NumberOfMultiples * (FirstMultiple + LastMultiple) / 2;\n}\n\n\nint main(void)\n{\n    long N = 1000;\n    long Sum = SumOfMultiples(N, 3) + SumOfMultiples(N, 5) - SumOfMultiples(N, 3*5);\n\n    printf("%ld\\n", Sum);\n}\n

\n

当你做其他欧拉计划问题时，你应该寻找类似的想法。

\n