プログラマーな日々

プログラマーをやっています。好きなものは、C#, TaskChute Cloud, WorkFlowy, Backlog, AWSです。

1.1.1 自然数と素数(その1)

エラトステネスの篩(ふるい)

ある自然数Nまでのすべての素数を求めるには、

  1. 最小の素数2で割り切れる数、すなわち偶数を消去する。
  2. 3の倍数を消去する。
  3. これを√Nまで繰り返し、順次割り切れる数を消していくと、最後に素数だけが残る。*1

偶素数

2は唯一の偶数の素数で「偶素数」と呼ばれる。

*1:[N]はNを越えない最大の整数を表し、「ガウスの記号」と呼ばれる。