プロジェクト・オイラー

Project Euler

URL	projecteuler.net
タイプ	問題解決ウェブサイト
設立者	Colin Hughes
営利性	非営利
登録	無料
開始	2001年10月5日

プロジェクト・オイラー（英: Project Euler、名称はレオンハルト・オイラー由来）は、数学やプログラミングなどに興味を持つ大人や学生が主な利用者であり、プログラミング (コンピュータ)による一連の計算問題の解決を目的としたウェブサイトである。 800以上の問題のほかに毎週末ごとに1問ずつ増えており、様々な難問が用意されているが、 一般的なスペックのパソコンで効率的なアルゴリズムを用いれば、いずれも1分未満で解ける。 正答回答者のみが各問題の掲示板を閲覧できる。 2001年に創設されて以来世界的な知名度と人気を得ており、2013年10月の時点では世界中から34万人以上の利用者（最低1問以上の正答者）を有する。 利用者は正答数に応じて最大16のレベルが振り分けられ、各々の進捗状況を確認できる。

サイト内の問題はAPLのプログラミングコンテストでの使用実績があり、オンライン整数列大辞典では68問を引用している。

問題解答例

最初の問題

10未満且つ、3または5の倍数は、3、5、6、9であり、左の総和は23である。

同様に、1000未満且つ、3または5の倍数の総和を求めよ。

上記の例は典型的な問題よりもはるかに易しいが、ここでは効率的なアルゴリズムにより本質的な違いを例示するために挙げる。 力まかせ探索アルゴリズムは、1000未満のすべての自然数を調べ、基準値の総和を算出する。 以下に、簡単な擬似コードを示す ：

Set TOTAL to 0;
for every number NUM from 1 to 999 do
  if NUM mod 3 = 0 or if NUM mod 5 = 0 then
    add NUM to TOTAL;
output TOTAL

難問解答の際には、効率的なアルゴリズムがより重要になる。 上記の場合は、包除原理と閉形式総和により、1000回のループ文処理を避ける。

${\begin{aligned}\mathrm {sum} _{\text{3 or 5}}(n)&=\mathrm {sum} _{3}(n)+\mathrm {sum} _{5}(n)-\mathrm {sum} _{15}(n)\\\mathrm {sum} _{k}(n)&=\sum _{i=1}^{\left\lfloor {\frac {n-1}{k}}\right\rfloor }ki\\\sum _{i=1}^{n}ki&=k{\frac {(n)(n+1)}{2}}\end{aligned}}$

この場合、$\mathrm {sum} _{k}(n)$は$n$未満の$k$の倍数の総和を示す。 ランダウの記号による記法では、前述の力まかせ探索アルゴリズムはO(n)、上記の効率的なアルゴリズムはO(1)と示す。

外部リンク

• 公式サイト
• Jakumo : ロシア版
• ルーマニア版