2011-02-23 POJ-1811: Prime Test PKU keyword 素因数分解 問題概要 N(<2^54)が与えられる。Nが素数ならその旨判定し、そうでないなら最小の素因数を求める問題。 解法 まずは2^19(この数字は適当)以下の素数を列挙してNの因数であるかどうか試す。続いてMiller-Rabinで素数判定する。合成数だと判定されたらPollard's rhoで約数を検出することを繰り返す。オーバーフローしないように乗算を加算で実装した(powと同じような方法)。 感想 一応通ったけど、まだ遅い。100msを切るのを目標に改良を加えていきたい。