http://projecteuler.net/index.php?section=problems&id=291
http://d.hatena.ne.jp/inamori/20100518/p1の続き。
同じようなことをやっているはてなダイアリーProject Euler 41、高速な素数判定に書いてあった。pow(a, b, c)という関数でab % cが計算できるそうで。それを使ってMiller-Rabin法を実装してみた。ホントだ、いきなり倍近く素数判定が速くなった。
ただ、Problem 291はこれでも1時間くらいかかりそうだし、Problem 41は実際には7桁以下だけ考えればいいので、遅い素数判定法でも一瞬で答えが出る。
