歐拉計劃

歐拉計劃
Project Euler

網站類型	解題類網站
創始人	Colin Hughes
網址	projecteuler.net
商業性質	非盈利
註冊	免費
推出時間	2001年10月5日​（2001-10-05）

歐拉計劃（Project Euler）是一個解題網站，站內提供了一系列數學題供用戶解答，解題的用戶主要是對數學和計算機編程感興趣的成年人及學生。其主旨為鼓勵、挑戰和培養愛好數學的人的技能和樂趣。目前該站包含了七百多道不同難度的數學題。每一題都可以通過計算機程序在1分鐘內求出結果。該網站自2001年起定期增加新的題目，每題都有對應的討論區，只有註冊用戶在正確提交了這題的答案後才能進入。 網站設立了6個排行榜，其中的歐拉人（Eulerians）排行榜的分數需要最新題目的前50位解答者才能獲得。歐拉計劃不希望在站外分享題目的答案。

例題與解答

歐拉計劃的第一題是：

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

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

雖然這題比歐拉計劃大多數題目要容易的多，我們仍然可以用它來分析不同解題方法的效率。

用 $O{\bigl (}n{\bigr )}$ 的窮舉法來測試1000以下的所有符合條件的自然數，再將它們相加就能得到這題的結果。這很容易實現，用以下兩種不同的編程語言都能用很快求解出答案。

Python：

print(sum(i for i in range(1000) if i%3 == 0 or i%5 == 0))

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多次運算，獲得 $O{\bigl (}1{\bigr )}$ 的時間複雜度。

$sum(n)=\sum _{i=1}^{\lfloor {\frac {n}{3}}\rfloor }3i+\sum _{i=1}^{\lfloor {\frac {n}{5}}\rfloor }5i-\sum _{i=1}^{\lfloor {\frac {n}{15}}\rfloor }15i$

$\sum _{i=1}^{n}ki=k{\frac {(n)(n+1)}{2}}$

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以下所花費的時間是相等的。

外部連結

• 歐拉計劃首頁 （頁面存檔備份，存於網際網路檔案館）