primenumber

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

初めに こんにちは、keymaleです。今回はpythonでの素数数え上げです。通常のやり方から、高速数え上げ(エラトステネスの篩←ふるいって読みます)を実装します。atcoderのD問題で2回目にこの素数数え上げに関する問題が出たので、備忘録として書いておきます。素因数分解も紹介しておきます。 通常の素数列挙 通常の方法は以下になります。 2は自明の素数として、3から2個ずつ、3,5,7,9,1 […]