7 エラトステネスのふるい

「エラトステネスのふるい」とは素数を求める古典的な方法である．例えば，25まで の素数は次のようにして求める．ただし，1は素数ではない．

1. はじめに，2〜25までの整数を用意する．
   

   2

   3

   4

   5

   6

   7

   8

   9

   10

   11

   12

   13

   14

   15

   16

   17

   18

   19

   20

   21

   22

   23

   24

   25

2. 最小の素数である左端の2を残して，その倍数を消去する．
   

   2

   3

   5

   7

   9

   11

   13

   15

   17

   19

   21

   23

   25

   
   これで2の処理は終了．
3. つぎに小さい素数である2の次の3を残して，その倍数を消去する．
   

   2

   3

   5

   7

   11

   13

   17

   19

   23

   25

   
   これで3の処理は終了．
4. つぎに小さい素数である3の次の5を残して，その倍数を消去する．
   

   2

   3

   5

   7

   11

   13

   17

   19

   23

   
   これで5の処理は終了．
5. 　これを繰り返すと，25までの素数がのこる．
   

   2

   3

   5

   7

   11

   13

   17

   19

   23

ホームページ: Yamamoto's laboratory
著者: 山本昌志