歐拉計畫

歐拉計畫（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)。