エラストテネスの篩
エラストテネスの篩
初の数学系の内容
概要
ある整数 x に対して、いくつ素数を持っているのかを見つける方法。
- まず、エラストテネスは何を篩にかけるのか？
1 から x までの整数の合成数をふるいにかける。← つまり、素数を探す。
前提
- 1は素数では無い。
- ある、整数aの約数は ${ \sqrt{a}}$ までの整数とそれ以降のペアで構成されている。
手順
例) 1~100までの素数を探す。
1. まず、１は素数では無いので、消去
2. ${ \sqrt{a}}$ を計算 → 10 (この数字まで、調べれば良い。)
2. １番目の素数２より大きい２の倍数を篩にかける。
3. 2の次に大きい素数３より大きい３の倍数を篩にかける。
4. 3の次に大きい素数5より大きい５の倍数を篩にかける。
5. ５の次に大きい素数７より大きい７の倍数を篩にかける。
6. 7の次に大きい素数１１より、、、
11は${ \sqrt{a}}$ より大きい！！ので、ここで、STOP！！
※なぜ、${ \sqrt{a}}$ で終わるのか： ${ \sqrt{a}}$ ~ 100までの約数が存在する整数は${ \sqrt{a}}$ までの手順で前提で述べた様に、約数のペアの内、前半の部分の約数により、篩にかけられているはずである。何が言いたいかというと、約数の存在しない整数、つまり素数のみこれまでの手順が残されてるはずである。