素数の見つけ方「エラトステネスのふるい」
素数コラム
ふるいで素数だけを残す
エラトステネスのふるいは、古代ギリシャの学者エラトステネスが考えたとされる、素数を順番に見つける方法です。粉をふるいにかけて細かい粒だけを残すように、数の表から「素数でない数」を消していき、残った数を素数とします。
手順
- 1 から 100 までの数を並べ、1 を消します（1 は素数ではありません）。
- 残っている一番小さい数 2 は素数です。2 を残して、2 の倍数（4, 6, 8, …）をすべて消します。
- 次に残っている一番小さい数 3 は素数です。3 の倍数（6, 9, 12, …）を消します。
- 同じように 5、7 の倍数を消します。
- 11 まで来たら終わりです。11×11＝121 は 100 を超えるので、11 以上の数の倍数はもう全部消えているからです。残った数がすべて素数です。
結果：1〜100の素数
緑色の数が、ふるいに残った素数です。全部で25個あります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
なぜ √n まで調べれば十分なのか
ある数 n が素数でないなら、n＝a×b と分けられます。このとき a と b の両方が √n より大きいと、a×b は n より大きくなってしまいます。つまり、素数でない数は必ず √n 以下の約数を持っています。だから √n までの素数の倍数を消せば、残りはすべて素数だとわかるのです。
素数占いの計算でも同じ考え方を使っています。8桁の誕生数が素数かどうかは、約4,500（√20,000,000）までの数で割り切れるか調べれば判定できます。
今でも使われている
エラトステネスのふるいは2000年以上前の方法ですが、決まった範囲の素数をまとめて見つける方法として、今でもコンピュータのプログラムでよく使われています。
あなたの運命の素数を占う