プログラマーな日々

I'm a Cloud Architect and Developer, and a trainee of the network engineer training course. I have certified by AWS and Cisco (SAA/SOA/DVA/CCNA). I especially have highly motivated to reduce toils.

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

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

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

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

偶素数

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

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