Project Euler 146
ずいぶん長い間解けないでいた問題をとりあえず解きました。forum を読んだ感じだと，これは素数判定をする問題だったようですね。
素数判定をやらない解き方を紹介してみます。遅いです。あと細かい調整や最適化がいくつかありますけどたいして面白くないので省略します。
Shanks-Tonelli
以下 p は 2, 5 以外の 150,000,000 未満の素数。
100 * n^2 + k (k = 1, 3, 7, 9, 13, 27) がどんな p でも割り切れず，100 * n^2 + 21 がある p で割り切れるような n < 15,000,000 をすべて見つければよい。
すべての p について
- ある k について n^2 + k が p の倍数になる n
- n^2 + 21 が p の倍数になる n
が見つかればよい。k を止めるごとに，そのような n を一つ求めれば残りは m * p ± n として一般形が求められる。n を一つ求めるのは Shanks-Tonelli のアルゴリズムにより p の対数の多項式(たぶん二次か三次)くらいの時間でできる。
上記の二項目について，それぞれ n がそうなるかならないかを bitset にメモしていって，最後にどの p についても「1 を満たさないが 2 を満たす」ような n をすべて足せばよい。
sieve
t[n] = n^2 + k と初期化しておいて，n < k/2 のときは愚直に t[n] の素因数 p を探す。見つけたら p | n^2 + k ということだから，m * p ± n の形の n' すべてについて t[n'] を p で割れるだけ割る。
これを n = 0 から順番にやっていくと，k/2 より大きい n については，n にたどり着いたときには t[n] は素数になっている(ような気がする)。だから n > k/2 のときは t[n] が素因数になっているのでそれを p として同じようなことをやる。このとき，もしも t[n] = n^2 + k のままであれば n^2 + k が素数だったということになる。
あとはだいたい同じ。
