素数と仲良しになる3つのプログラム

競技プログラミングでは、素数に関わる問題が多くある。

例えば、a^b は c^dで割り切れるかどうか、という問題。
ただし a,b,c,dはそれぞれ10⁹ まで。

この場合普通にa^bは計算出来ない(10億の10億乗になってしまうので)。
そういう時はaとcを素因数分解していく必要がある。

まあそういった問題はよくあるので、
よくつかう素数に関する関数をPythonで書いた。

素因数分解

素数の場合に√nまで回すので、
10 ¹⁴くらいまでは(Pythonだと)一瞬で判定できる。

素数判定

これも、素数の場合に√nまで回すので、
10 ¹⁴くらいまでは一瞬で判定できる。

nまでの素数テーブルをつくる

10 ⁷くらいまでは一瞬で作れる。

まとめ

もっと高速化しようと思えばできるけど、
書くコストと複雑さ、消費メモリ的にはこれくらいが実用的だと思う。