素数について書いてきました。
しかし、もう少し基本を見ておかないと、解かりづらい（私が理解できなくなる）ので、・・・
「素数の篩」について確認しておきます。
以下の表は各整数の因数を列挙したものです。
先頭行のmの前に書いてある数が各篩の間隔になります。
自分自身以外の因数を持たない数が素数となります（赤字）。
篩を通り抜けた数が素数ということです。
n 2m 3m 4m 5m 6m 7m 8m 9m 10m 11m 12m 13m 14m 15m 16m 17m 18m 19m 20m
2 2
3 3
4 2 4
5 5
6 2 3 6
7 7
8 2 4 8
9 3 9
10 2 5 10
11 11
12 2 3 4 6 12
13 13
14 2 7 14
15 3 5 15
16 2 4 8 16
17 17
18 2 3 6 9 18
19 19
20 2 4 5 10 20
ここで私が注目したのは篩の目の方です。
2mの目は2m+1,
3mの目は3m+1,+2,
この二つ目を合成すると
6m+5,+1(7 mod 6),
この目に5mを合成すると
30m+1(31 mod 30), +7, +11, +13, +17, +19, +23, +29,
素数の篩の目は2m+1に3m,5m,7mと合成を繰り返すたびに、
繰り返しの単位を2, 6, 30, 210, 2310, ・・・と拡大させて行く。
これが成り立つのは、篩どうし又はその合成したもとが互位に素であるからである。
