POJ-1811: Prime Test

keyword

素因数分解

問題概要

N(<2^54)が与えられる。Nが素数ならその旨判定し、そうでないなら最小の素因数を求める問題。

解法

まずは2^19(この数字は適当)以下の素数を列挙してNの因数であるかどうか試す。続いてMiller-Rabinで素数判定する。合成数だと判定されたらPollard's rhoで約数を検出することを繰り返す。オーバーフローしないように乗算を加算で実装した(powと同じような方法)。

感想

一応通ったけど、まだ遅い。100msを切るのを目標に改良を加えていきたい。