python~素数列挙(エラトステネスの篩)と素因数分解~

初めに

こんにちは、keymaleです。今回はpythonでの素数数え上げです。通常のやり方から、高速数え上げ(エラトステネスの篩←ふるいって読みます)を実装します。atcoderのD問題で2回目にこの素数数え上げに関する問題が出たので、備忘録として書いておきます。素因数分解も紹介しておきます。

通常の素数列挙

通常の方法は以下になります。

2は自明の素数として、3から2個ずつ、3,5,7,9,11…の順に自身より小さい素数で割れるか計算して、すべて割れなければ、新たな素数としてリストに追加します。

高速素数列挙(エラトステネスの篩)

次にエラトステネスの篩です。

調べたい最大値まで1ずつ増えるリストを作成し(最小値は2)、リストの最小値でリストをすべて割っていき、割り切れるものは削除し、割っていた数を素数リストに追加します。そして、削除後のリストの最小値で、またリストを割っていき、割り切れたものを削除して、割っていた値を素数リストに追加。これを√nまで繰り返します。

素因数分解

素因数分解は素因数分解したい数nに対して2から√nまで順番に割り切れなくなるまで割って、割った回数を出力します。コードは以下の通りです。