Anyable

この辺りから、愚直に力任せのロジックを書くと処理時間が大変なことになり始める。

素数といえば「エラトステネスのふるい」
単純なのに高速なアルゴリズムの代表格だと思う。

「エラトステネスのふるい」の形で算出される素数はN以下の数字ということになる。
必要となるのはX番目の素数であり、その素数がどの程度の大きさか？と言うのは分からない。
なので、「エラトステネスのふるい」を使う場合でも【N以下】のNをいくつにすればいいか？が問題になってくる。
そもそも「エラトステネスのふるい」は高速ではあるが、メモリはそれなりに食うアルゴリズムである。

とは言え、所詮10001番めの素数なので気にせず100万までのエラトステネスのふるいをして、足りなければ試し割りで次の素数を・・・
みたいな感じでやればいいんじゃないすかね？
ちなみに、10001番目の素数は10万ちょっとくらいなので100万までの素数出しとけば余裕です。

100万までのエラトステネスのふるいをする場合のメモリ使用量だけ、考えておく。
1つの整数に1bit使うとすると1000000bit = 125000Byte = 約122KBとなる。
PCなら2桁くらい増やしても余裕そう！工夫すればメモリ抑えられるし。

なお「アトキンの篩」なる、より高速化されたアルゴリズムもあるらしい。（2003年発表とかなり新し目）
「エラトステネスの篩」と比較して10桁程度までの素数なら数倍程度の差がでるとのこと。

その他にも素数周りは様々な高速化テクニックがあるので、気になる人はGoogle先生に聞いて下さい。

---

参考にしたサイト

• エラトステネスの篩 - Wikipedia
• Sieve of Atkin - Wikipedia, the free encyclopedia

等差数列の和の2乗と2乗和の差を求める問題。

100までなんで、オーバーフローも気にせずfor文で回して求めればすぐに答えは出る。

等差数列にも2乗和にも公式があるらしい。

等差数列は知ってたけど、2乗和、というかファイルハーバーの公式というのは初めて聞いた。

---

参考にしたサイト

• ファウルハーバーの公式 - Wikipedia

何か問題文が回りくどい気がするけど、要は「1～20の整数の最小公倍数」を求める問題。

1. 最小公倍数を求めるには最大公約数を求めると楽になる。
2. 最大公約数を求めるにはユークリッドの互除法を使うと楽になる。

ユークリッドの互除法は2つの整数に付いて最大公約数を求めるアルゴリズムなので、これを3つ以上の整数に適用する必要がある。

整数abcの最大公約数（gcd）・最小公倍数（lcm）は次の性質を持つ。

gcd( a, b, c ) = gcd( gcd( a, b ), c )
lcm( a, b, c ) = lcm( lcm( a, b ), c )

また、最大公約数と最小公倍数には次の関係がある。 ※この関係は2つの整数についてのみ。

lcm( a, b ) = a * b / gcd( a, b )

以上のことから、1から20まで最小公倍数を順次求めていけばOK
（公倍数なので1はそもそも計算する必要は無いけど）

---

参考にしたサイト

• 最小公倍数 - Wikipedia
• 最大公約数 - Wikipedia
• ユークリッドの互除法 - Wikipedia

練習問題といえるような簡単な問題。
プログラムの基礎がわかっていればすぐに解ける。

が、こんな問題にも実は数学的要素がある。

「3もしくは5の倍数の和」とは「3の倍数の和 + 5の倍数の和 - 15の倍数の和」と言い換える事ができる。
「Yの倍数の和」とは、つまり等差数列の和と言い換えることができる。

等差数列の和は初項a・公差d・項数nがわかっていると以下の式で求められる。

sum = n / 2 * ( 2 * a + ( n - 1 ) * d )

1000未満の3の倍数は初項 = 3、公差 = 3、項数 = 333なので以下のように求められる。

333 / 2 * ( 2 * 3 + ( 333 - 1 ) * 3 ) = 166833

同様に5の倍数について、15の倍数に付いても求められる。

計算量を考えた場合、for文で回した場合はO(n)であるが、上記計算式で求めた場合はO(1)となる。
こんな感じで、数学的に問題を分解するとすごく簡単に解ける問題がProject Eulerの特徴と言える。

---

参考にしたサイト

• 等差数列 - Wikipedia