PRoxy Diary(2007-12-27)

_ [ICPC] Prime Checkerさて、最近流行っていた素数判定問題(以降PRIC)に対する僕の解法の紹介です。見たくない人は読み飛ばすと良いでしょう。 ソースコード: PRIC6.cpp この問題の目的はv[1]=1 v[i]=(v[i-1]+1234567890)%(2^31)(2 で定義されるv[i]を順に素数かどうかを判定していくことです。ここでまず高速な方法としてフェルマーテストやミラーラビン素数判定法が思いつくと思います。僕がいろいろ実験した限りでは、両者に速度の差が感じられなかったので、コード量の短いフェルマーテストを採用することにしました。 フェルマーテストは次のフェルマーの小定理を用いる方法です。(フェルマーの小定理) pを素数、aをpと互いに素な整数とする。このときa^(p-1)=1(mod p) これの逆、すなわち「a^(p-1)=1(mod p)ならばp