C语言 求 1000 以下所有 3 或 5 的倍数之和
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3847878/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find the sum of all the multiples of 3 or 5 below 1000
提问by fuddin
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. I have the following code but the answer does not match.
如果我们列出所有 10 以下的自然数是 3 或 5 的倍数，我们会得到 3、5、6 和 9。这些倍数的总和是 23。我有以下代码，但答案不匹配。
#include<stdio.h>
int main()
{
long unsigned int i,sum=0;
clrscr();
for(i=0;i<=1000;i++)
{
if((i%5==0)||(i%3==0))
{
sum=sum+1;
}
}
printf("%d\n",sum);
getchar();
return 0;
}
回答by JPMC
Rather than using range/loop based solutions you may wish to leverage more math than brute force.
而不是使用基于范围/循环的解决方案，您可能希望利用更多的数学而不是蛮力。
There is a simple way to get the sum of multiples of a number, less than a number.
有一种简单的方法可以得到一个数的倍数之和，小于一个数。
For instance, the sum of multiples of 3 up to 1000 are: 3 + 6 + 9 + ... + 999 Which can be rewritten as: 3* ( 1 + 2 + 3 + ... + 333)
例如，3 到 1000 的倍数之和为： 3 + 6 + 9 + ... + 999 可以重写为： 3* ( 1 + 2 + 3 + ... + 333)
There is a simple way to sum up all numbers 1-N:
有一种简单的方法可以将所有数字 1-N 相加：
Sum(1,N) = N*(N+1)/2
So a sample function would be
所以一个示例函数将是
unsigned int unitSum(unsigned int n)
{
return (n*(n+1))/2;
}
So now getting all multiples of 3 less than 1000 (aka up to and including 999) has been reduced to:
所以现在得到小于 1000 的所有 3 的倍数（也就是高达并包括 999）已减少为：
3*unitSum((int)(999/3))
You can do the same for multiples of 5:
您可以对 5 的倍数执行相同的操作：
5*unitSum((int)(999/5))
But there is a caveat! Both of these count multiples of both such as 15, 30, etc It counts them twice, one for each. So in order to balance that out, you subtract once.
但有一个警告！这两个计数都是两者的倍数，例如 15、30 等。它对它们计数两次，每个计数一个。所以为了平衡它，你减去一次。
15*unitSum((int)(999/15))
So in total, the equation is:
所以总的来说，等式是：
sum = 3*unitSum((int)(999/3)) + 5*unitSum((int)(999/5)) - 15*unitSum((int)(999/15))
So now rather than looping over a large set of numbers, and doing comparisons, you are just doing some simple multiplication!
因此，现在不是循环处理大量数字并进行比较，而是进行一些简单的乘法运算！
回答by martin clayton
Two things:
两件事情：
- you're including1000 in the loop, and
- you're adding one to the sum each time, rather than the value itself.
- 你在循环中包含了1000 个，并且
- 您每次都将总和加一，而不是值本身。
Change the loop to
将循环更改为
for(i=0;i<1000;i++)
And the sum line to
和总和线
sum=sum+i;
回答by Hugo Peixoto
Perhaps you should do
也许你应该做
sum += i // or sum = sum + i
instead of
代替
sum = sum + 1
Additionally, be careful when printing long unsigned ints with printf. I guess the right specifier is %lu.
此外，long unsigned int使用 printf打印s时要小心。我想正确的说明符是%lu.
回答by Eric Fortin
It should be sum = sum + iinstead of 1.
它应该sum = sum + i代替1.
回答by anil kumar
#include<stdio.h>
#include<time.h>
int main()
{
int x,y,n;
int sum=0;
printf("enter the valeus of x,y and z\n");
scanf("%d%d%d",&x,&y,&n);
printf("entered valeus of x=%d,y=%d and z=%d\n",x,y,n);
sum=x*((n/x)*((n/x)+1)/2)+y*((n/y)*((n/y)+1)/2)-x*y*(n/(x*y))*((n/(x*y))+1)/2;
printf("sum is %d\n",sum);
return 0;
}
// give x,y and n as 3 5 and 1000
回答by gkns
Just as an improvement you might want to avoid the loop altogether :
作为一项改进，您可能希望完全避免循环：
multiples of 3 below 1000 form an AP : 3k where k in [1, 333]
multiples of 5 below 1000 form an AP : 5k where k in [1, 199]
If we avoid multiples of both 3 and 5 : 15k where k in [1, 66]
如果我们避免 3 和 5 的倍数：15k 其中 k 在 [1, 66]
So the answer is : 333*(3+999)/2 + 199(5+995)/2 - 66*(15+990)/2 = 233168
So the answer is : 333*(3+999)/2 + 199(5+995)/2 - 66*(15+990)/2 = 233168
Why you might want to do this is left to you to figure out.
为什么你可能想要这样做由你来弄清楚。
回答by Dan Wills
Here's a python one-liner that gives the correct answer (233168):
这是给出正确答案的 Python 单行代码 (233168)：
reduce( lambda x,y: x+y, [ x for x in range(1000) if x/3.0 == int( x/3.0 ) or x/5.0 == int( x/5.0 ) ] )
回答by Cobi
Interesting fact of the difference in time between this 2 methods... The second method just calculate only with needed numbers and dont iterate through a loop. Example: 3 * (1+2+3+4...333) (Because 3 * 333 = 999 and 999 < 1000.
这两种方法之间时间差异的有趣事实......第二种方法仅使用所需的数字进行计算，而不是通过循环进行迭代。示例：3 * (1+2+3+4...333) （因为 3 * 333 = 999 且 999 < 1000。
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
Calc calculator = new Calc();
long target = 999999999;
sw.Start();
Console.WriteLine("Result: " + (calculator.calcMultipleSumFast(3,target) + calculator.calcMultipleSumFast(5, target) - calculator.calcMultipleSumFast(15, target)));
sw.Stop();
Console.WriteLine("Runtime: " + sw.Elapsed);
Console.WriteLine();
sw.Start();
Console.WriteLine("Result: " + (calculator.calcMultiplesSum(3, 5,1000000000)));
sw.Stop();
Console.WriteLine("Runtime: " + sw.Elapsed);
Console.ReadKey();
}
public class Calc
{
public long calcMultiplesSum(long n1, long n2, long rangeMax)
{
long sum = 0;
for (long i = 0; i < rangeMax; i++)
{
if ((i % n1 == 0) || (i % n2 == 0))
{
sum = sum + i;
}
}
return sum;
}
public long calcMultipleSumFast(long n, long rangeMax)
{
long p = rangeMax / n;
return (n * (p * (p + 1))) / 2;
}
}
回答by John Hascall
Using the stepping approach, you can make a version:
使用步进方法，您可以制作一个版本：
#include <stdio.h>
int main ( void ) {
int sum = 0;
for (int i = 0; i < 1000; i += 5) {
sum += i;
}
for (int i = 0; i < 1000; i += 3) {
if (i % 5) sum += i; /* already counted */
}
printf("%d\n", sum);
return 0;
}
which does a whole lot fewer modulocomputations.
它的modulo计算量要少得多。
In fact, with a counter, you can make a version with none:
事实上，使用计数器，您可以创建一个没有的版本：
#include <stdio.h>
int main ( void ) {
int sum = 0;
int cnt = 6;
for (int i = 0; i < 1000; i += 5) {
sum += i;
}
for (int i = 0; i < 1000; i += 3) {
if (--cnt == 0) cnt = 5;
else sum += i;
}
printf("%d\n", sum);
return 0;
}
回答by Abdullah Abdelmonem
int Sum(int N) {
long long c = 0;
N--; //because you want it less than 1000 if less than or equal delete this line
int n = N/3,b = N/5,u = N/15;
c+= (n*(n+1))/2 * 3;
c+= (b*(b+1))/2 * 5;
c-= (u*(u+1))/2 * 15;
return c;
}
