2011-07-21 1.1.1 自然数と素数(その1) オイラーの贈物 エラトステネスの篩(ふるい) ある自然数Nまでのすべての素数を求めるには、 最小の素数2で割り切れる数、すなわち偶数を消去する。 3の倍数を消去する。 これを√Nまで繰り返し、順次割り切れる数を消していくと、最後に素数だけが残る。*1 偶素数 2は唯一の偶数の素数で「偶素数」と呼ばれる。 *1:[N]はNを越えない最大の整数を表し、「ガウスの記号」と呼ばれる。