欧拉项目【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. 

The sum of these multiples is 23.Find
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倍左右的提升。具体的运行参数如下表：

最后的分析：

难道真的这样就完了吗？如果现在要求把1000改成1000000会怎样?我们还是虚心看看别人写的东西吧！要想知道速度快不快还得和别人的比较才行。

再回到我最初的想法：

序列1+序列2-序列3

如果现在真的要求把1000改成1000000，我还有从3,6
,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)

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)，要不要这么狠，比我的汇编代码还快，我下巴都快掉了，这就是一个高中送分的题啊，被我们想得这么复杂，笔算都可以很快算出来啊。

不过有一点是值得我们思考的，在学习了很多是数学知识后我们没有很好的将它们利用起来，遇到问题就以为用暴力的方式解决，不仅成效不高,还达不到优雅美观，有失个人风范。而欧拉项目的目的是用数学帮助你运用优雅而有效的方法,实现漂亮而快速的代码。数学什么时候都不会过时。