欧拉计划（Project Euler）

创始者：Colin Hughes

推出时间：October 5, 2001

欧拉计划（Project Euler）是一个解题网站，站内提供了一系列数学题供用户解答，解题的用户主要是对数学和计算机编程感兴趣的成年人及学生。目前该站包含了380多道不同难度的数学题，每一题都可以通过计算机程序在1分钟内求出结果。该网站自2001年起定期增加新的题目，每题都有对应的讨论区，注册用户在正确提交了某题的答案后才能进入该题的讨论区。站内根据完成题目的数量将用户分为6个级别，设立了6个排行榜，并用正多面体和球体来表示不同的级别。另外还设有一个欧拉人（Eulerians）排行榜，只包含在最新的25题里作出13题以上的用户。

例题与解答

欧拉计划的第一题是：

列举出10以下所有3或5的倍数，我们得到 3, 5, 6 和 9。他们的和是23。

求1000以下所有3或5的倍数之和。

虽然这题比欧拉计划大多数题目要容易的多，我们仍然可以用它来分析不同解体方法的效率。

用穷举法来测试1000以下的所有自然数，再将它们相加就能得到这题的结果。这很容易实现，用以下两种不同的编程语言都能很快求解出答案。

Python：

print sum(filter(lambda x:x % 3 == 0 or x % 5 == 0, xrange(1, 1000)))

C++：

#include <iostream>

using namespace std;

int main( ) {

int sum = 0;

for (int i = 0; i < 1000; i++)

if ( i % 3 == 0 || i % 5 == 0 )

sum += i;

cout << sum << endl;

return 0;

}

但如果用排容原理进行求和，就可以减少1000多次运算。

Python 实现：

def sum1toN(n):

return n * (n + 1) / 2

def sumMultiples(limit, a):

return sum1toN((limit - 1) / a) * a

sumMultiples(1000, 3) + sumMultiples(1000, 5) - sumMultiples(1000, 15)

采用这种方法，计算10,000,000以下或1000以下所花费的时间是相等的。若用大O符号来描述两种方法的优劣，那么穷举算法为O(n)而高效的算法为O(1)。