poj 1811 ちょっと考えた。 2007/09/21

1811 -- Prime Test

素数を扱う問題だったので、なんとなくできるかなと思ったのが運のツキで、かなりてこずりました。
まず、だいいちに自分に数学の知識がないことが原因だと思いましたが、javaで解く場合には、大きな数の素数を判定する方法はjavaのほうで用意されているおり、あとは、最小の約数（素数の）を求めるところがキモのようです。

この問題を解くための基本のアイデアはあったのに、時間超過で泣かされて、もう少しもう少しとやり続けてかなりの時間の睡眠時間を削りました。

参考
Cozy Ozy - ハマッタ(;´д｀)
にあるように

(1)
素数判定
(2)
小さい素数で割り続けて判定

という流れは変わらずです。
（２）でいかに効率的にするかがキモだと思います。


で、実は、素数の判定が遅いからだめだと信じきって(javaの実装はだめだと信じきって)いろいろ素数判定のためのコードをみつけてきてはためしたのですが、もちろんはやければはやいほどいいのですが、（２）を劇的にはやくすることはできませんでした。

（２）をどういうふうに効率よくおこなうかといいますと、素数で割ればいいのですから、素数テーブルをもたせればよい、というのもありますが、簡単なのは、奇数のみで、割ること、つぎに奇数でなおかつ素数である可能性が高そうな値で割ること、に専念すればよしです。

12章 素因数分解アルゴリズムをみたら、あーなるほどでした。

30n＋１、30n＋７、30n＋11、30n＋13、30n＋17、30n＋19、30n＋23、30n＋29
12章 素因数分解アルゴリズム

ある意味、簡単かもしれませんね...

javaを使う場合は、直接の素数の判定はBigIntegerの実装を使い、（２）を解くための実装は上記のアルゴリズムでいけばOKです。


素数関連
ミラー-ラビン素数判定法 - Wikipedia
The Las Vegas algorithm/method at DataStructures
18446744073709551615
ポラード・ロー素因数分解法 - Wikipedia
The Prime Database: The List of Largest Known Primes Home Page
PollardRho.java
〜プログラム@Bal4u〜: 素数の判定 （ペパン判定法）　pepan
〜プログラム@Bal4u〜: 素数判定 Miller-Rabinテスト