Project Euler 1〜100 解説ノート
Project Euler の1問目から100問目まで、1日1問ずつ解いていきます。各記事では、必要な前提知識、解法の導き方、計算量、C++17 と Python 3 の実装をまとめます。
各記事には解き方と答えがそのまま載っています。コミュニティの慣習にならい、このシリーズは1〜100問目だけを扱います。
問題は Project Euler のもので、CC BY-NC-SA 4.0 でライセンスされています。Motitory は Project Euler とは関係がありません。
Project Euler 1: 3または5の倍数の和をO(1)で求める
1000未満で3か5で割り切れる数の和を、ループを使わずに包除原理と等差数列の和で求めます。C++17とPython 3の実装、正しさの証明、整数の範囲まで扱います。
Project Euler 2: 偶数のフィボナッチ数だけを足す
フィボナッチ数列では3項ごとに偶数が現れることを証明し、偶数項どうしの漸化式 E(k) = 4E(k−1) + E(k−2) を導いて、400万以下の偶数項だけを足します。C++17とPython 3の実装、正しさの証明、整数の範囲まで扱います。
Project Euler 3: 割れるだけ割って最大の素因数を求める
小さい数から割れるだけ割っていく試し割り法で、12桁の整数の最大の素因数を求めます。最後に残る値がなぜ素数なのかの証明、√n の反復回数の上限、64ビット整数の範囲、C++17とPython 3の実装まで扱います。
Project Euler 4: 3桁の数2つの積で最大の回文数を大きい方から探す
3桁の数2つの積のうち最大の回文数を、大きい積から順に探して枝刈りしながら求めます。枝刈りで答えを見落とさない理由の証明、偶数桁の回文数と11の関係、整数の範囲、C++17とPython 3の実装まで扱います。
Project Euler 5: 1から20までのすべてで割り切れる最小の数を最小公倍数から組み立てる
1から20までのすべての数で割り切れる最小の正の整数を、1つずつ試すのではなく、ユークリッドの互除法と lcm(a, b) = a / gcd(a, b) × b の繰り返しで組み立てます。この方法がちょうど最小公倍数を与える理由の証明、整数の範囲、C++17とPython 3の実装まで扱います。