読者です 読者をやめる 読者になる 読者になる

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

ProgrammingContest Python

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

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

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

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

素因数分解


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

素数判定


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

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


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

まとめ

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