素数判定器を作った
みなさんは今日が素数かどうか気になったことはありますよね?私もあります。そこで簡単にツールを作りました。
Algorithm
使用したアルゴリズムはAKS素数判定法とミラー–ラビン素数判定法です。
Performance
手元の環境では下記のようになりました。やはり確率的アルゴリズムであるミラー–ラビン素数判定法の方が高速ですね。(ご存知の通り2021年12月21日は素数でしたね)
$ time ./target/release/pn -a aks 20211221 true ./target/release/pn -a aks 20211221 5.23s user 0.06s system 95% cpu 5.512 total $ time ./target/release/pn -a miller-rabin 20211221 true ./target/release/pn -a miller-rabin 20211221 0.00s user 0.00s system 69% cpu 0.004 total