欧拉项目【ProjectEuler】系列-第一题
----人既无名
既然是第一次，当然要写个基本的介绍咯。
欧拉项目是一系列挑战数学/计算机编程的问题. 需要的不仅仅是数学见解,还要利用计算机编程技巧,需要解决大多数问题，当然，数学帮助你运用优雅而有效的方法,实现漂亮而快速的代码。
欧拉项目的网站是http://projecteuler.net，只要上去注册一个账号就可以开始你的欧拉之旅了，当你把一个问题解决之后就可以参加该问题的讨论，说说你的解决办法，看看其他人的处理思路咯。言归正传，开始欧拉项目的第一题咯。
Problem 1：If
we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9.
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.
the sum of all the multiples of 3 or 5 below 1000.
意思就是：求出1000以下3或者5的倍数的自然数的和。
分析1：
3的倍数可以简单表示为 n%3==0.
5的倍数可以简单表示为 n%5==0.
3或者5的倍数就可以表示为 (n%3)&&(n%5)==0
因此，最简单的办法就是遍历1-999，判断该数是不是3或者5的倍数，是就加上，不是就跳过
int Fuc1()
{//Lazy way
int sum = 0;
int i=0;
for( i = 1; i < 1000; ++i)
if(0==((i % 3) && (i % 5)))
sum += i;
return sum;
}
分析2：
1000以下3的倍数
序列1:3 6 9 12 15 18 ... 999
5的倍数有
序列2:5 10 15 ... 995 （注意是1000以下，不包括1000）
我们是不是可以把这些数加起来作为最终的和呢？
很显然，两个序列中都有
序列1:15 30 ... 990（3和5的公倍数，也就是15的倍数）。
因此如何把序列1和序列2 加起来和还要减去序列3.
sum=序列1+序列2-序列3;
这个也是我最初的思路。整个代码也就是
int MyFuc()
{
int sum = 0;
int i;
//序列1
for(i=3;i<1000;i+=3)
{
sum+=i;
}
//序列2
for(i=5;i<1000;i+=5)
{
sum+=i;
}
//序列3,注意是减去
for(i=15;i<1000;i+=15){sum-=i;}
return sum;
}
分析3：
可能会有人注意到，在我的第二个分析实现是第三步是减去序列3，也就是序列3的数实际上被访问了两遍，有没有更好的办法只将所有的目标数只访问一遍就能求出结果呢？在来分析这些序列的特点
3 5 6 9 10 12 15 18 20 21 24 25 27 30 33 35 36 39 40 ...
除去3的倍数，即序列1，剩下的部分可以发现分为两个序列
5 20 35 ...
10 25 40 ...
因此优化后的代码为
int MyFuc2()
{
int sum = 0;
int i;
//序列1
for(i=3;i<1000;i+=3)
{
sum+=i;
}
//序列2
for(i=5;i<1000;i+=15)
{
sum+=i;
}
//序列3
for(i=10;i<1000;i+=15)
{
sum+=i;
}
return sum;
}
当然我们完全可以把这段代码用汇编来实现，这是我用VC6下实现的汇编代码：
int Fuc3(){
int sum;
_asm{
xor edx,edx ;sum
mov eax,3
A: cmp eax,1000
jnl B
add edx,eax
add eax,3
jmp A
B: mov eax,5
B1: cmp eax,1000
jnl C
add edx,eax
add eax,15
jmp B1
C: mov eax,10
C1: cmp eax,1000
jnl D
add edx,eax
add eax,15
jmp C1
D: mov sum,edx
}
return sum;
}
此时我已经沉浸在胜利的喜悦中，因为我的代码优化已经达到了汇编级别，将上述4个函数分别运行1000000次测试结果显示,从最开始需要6.898秒到现在只要0.618秒，运行的速度得到了10倍左右的提升。具体的运行参数如下表：
| 函数 | 运行特点 | 运行时间(s) |
| Fuc1() | 最原始的方法 | 6.898 |
| MyFuc() | 序列1+序列2-序列3 | 2.093 |
| MyFuc2() | 优化后的序列法 | 1.569 |
| Fuc3() | 汇编优化 | 0.618 |
| Fuc5() | 等差数列求和公式 | 0.103 |
最后的分析：
难道真的这样就完了吗？如果现在要求把1000改成1000000会怎样?我们还是虚心看看别人写的东西吧！要想知道速度快不快还得和别人的比较才行。
再回到我最初的想法：
序列1+序列2-序列3
如果现在真的要求把1000改成1000000，我还有从3,6
,9遍历到999999吗？
,9遍历到999999吗？
3,6,9,...,999999
5,10,15,...,999995
15,30,...,999990
这三个序列都是等差数列啊，高中不就学过等差数列求和的方法吗？
对于等差数列a1,a2,...,an,其中an=a1*dn,他们的和Sn为：
Sn=(a1+an)*n/2;
或者
Sn=a1*(1+dn)*n/2;
等等，通过这个公式是就可以快速求出3个等差序列的和
如，对于序列1：
999/3=333
序列1的和=3+6+9+...+333=3*（1+333）*333/2
同样
999/5=199(取整即可)
序列2的和=5+10+...+995=5*（1+199）*199/2
999/15=66
序列2的和=15+30+...+990=15*（1+66）*66/2
sum=3*（1+333）*333/2+5*（1+199）*199/2+15*（1+66）*66/2;
设计一个求序列和的函数SumSeiresBy(int
n)
n)
int SumSeiresBy(int n)
{
int p=999/n;
return n*(1+p)*p/2;
}
最终求和可以写成
int Fuc5()
{
int sum;
sum=SumSeiresBy(3)+SumSeriesBy(5)-SumSeresBy(15);
return sum;
}
运行1000000次的时间为0.103秒(见表1)，要不要这么狠，比我的汇编代码还快，我下巴都快掉了，这就是一个高中送分的题啊，被我们想得这么复杂，笔算都可以很快算出来啊。
不过有一点是值得我们思考的，在学习了很多是数学知识后我们没有很好的将它们利用起来，遇到问题就以为用暴力的方式解决，不仅成效不高,还达不到优雅美观，有失个人风范。而欧拉项目的目的是用数学帮助你运用优雅而有效的方法,实现漂亮而快速的代码。数学什么时候都不会过时。