Project Euler——Problem 1

daybreakcx posted @ 2009年7月14日 00:10 in Prject Euler , 846 阅读

原题与答案：

Problem 1

05 October 2001

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.

Answer:233168

分析与解答：

这个题目描述很简单，是求小于1000的所有3或者5的倍数的和，第一个题就是a+b性质的，很容易过，刚开始我直接利用容斥原理笔算求出了结果。首先是小于1000的3倍数的和 sum1=3+6+...+999=(3+999)*(999/3)/2=166833 ，接着是小于1000的5倍数的和 sum2=5+10+...+995=(5+995)*(995/5)/2=99500 ，最后是小于1000的15的倍数 sum3=15+30+...+990=(15+990)*(990/15)/2=33165 。于是我们要的结果 sum=sum1+sum2-sum3=166833+99500-33165=233168 。

当然，这个题目用C写一下也不难，很容易就可以得到代码：

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