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

プログラマーな日々

プログラマーをやっています。好きなツール:WorkFlowy、好きな言語:C#、好きなサービス:Backlog、好きなAWS:AWS Lambda。

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

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

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

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

偶素数

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

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