エラトステネスの篩い

  素数は整数論の中でも最も基本的な対象です。素数の分布を調べるのは中々難しい問題ですが,素数の表を作る方法として,古くから知られているエラトステネスの篩いと言う方法があります。ここではこれについて説明します。


 エラトステネス(-275〜-194)は 地球の大きさを測ったことで知られる古代ギリシアの数学者です。この篩いについては,ニコマコス(100頃)の「算術入門」第1巻13章にその記述があるそうです。

 それによると,この方法は,奇数の表

3,5,7,9,11,13,15,17,19,21,23,25,27,...

を作り,その中から,3の倍数を順次除き,次に5の倍数を順次除き残ったものが素数であるとするものです。


 簡単な方法ですが,プログラムの問題としては基本的でよく扱われるものです。

素数とその性質

 素数とその基本的な性質から説明しましょう。

 1より大きい自然数2,3,4,...の中で,真の約数を持たない数を素数(prime number)と言います。ここで真の約数と言うのは,1とその数自身ではない約数のことです。

 2や3は1とそれ自身以外の約数を持ちませんから,これらは素数です。他方,素数でない2以上の自然数を合成数と言います。例えば,4は2という真の約数を持ちますから,素数ではありません。すなわち合成数です。

 1は特別な数で,素数でも合成数でもありません。

一般に,mが合成数とは,1<s<m,1<t<m となる自然数 s,t に対して

m=s*t

と表されることを意味しています。逆に,素数はこのような分解が出来ないものとも言えます。

 素数や合成数と言い方は,数が素数と言う元素によって乗法的に作られていると言う考え方の反映です。実際,2以上の自然数は素数の積として表すことが出来ますが,その分解の仕方は順序の違いを無視すればただ一通りです。(この事実を素因数分解の一意性と言います。)

 例えば,30は

30=2*3*5

と表されますが,30の素数の積への分解はこれ以外ありません。(勿論,3*2*5や5*2*3と言った分解もありますが,これらは乗法の順序を変えただけなので,同じ分解と見ます。)ここで,30は2,3,5と言う数の元素(=素数)を使って構成されていると見られる訳です。

エラトステネスの篩いの原理

 エラトステネスの篩の原理は素数を見つける代わりに合成数を除いていくものです。つまり,

1より大きい数の表から合成数を除き,残ったものが素数

と言うものです。大変簡単な原理ですから,100以下の素数をすべて見つける位の問題なら,手で行っても簡単に実行できます。しかし多くの素数をこの方法を使って手計算で行うのは大変です。しかし,このような問題はコンピュータは大変得意です。コンピュータを使えばかなり大きな数以下の素数をこの方法ですぐに計算できます。エラトステネスの篩は古代の方法ですが,現在でも素数表を作るときには使われている方法です。

 いくらコンピュータが高速でも大きな素数表を作る場合,効率的な方法を考える必要があります。上の原理で素数表を作る場合の,なるべく効率的な具体的方法を考えましょう。考えるべきポイントは次です。

  1. どの数の倍数を除くか
  2. どの倍数を取り除くか

1.どの数の倍数を取り除くか

 ある数の真の倍数はすべて合成数ですから,ある数mを取ってその2倍,3倍,...と取り除くわけですが,もしmが合成数だとすると,mとmの倍数は既に取り除かれています。ですから,合成数の倍数は取り除く必要はありません。ですから,

素数の倍数のみ取り除けば良い

と言うことになります。真の倍数を取り除くことを篩うと言うことにします。この用語を使うと,

素数でのみ篩えば良い

と言うことになります。

 ところで,この篩う素数をどのようにして見つければ良いでしょうか。実はこれは極めて簡単です。今のように小さい方の素数から順に篩って行った場合,pまで篩ったとすると,pより大きい数で取り除かれていない最小の数は素数になります。実際,qがpより大きい数で取り除かれていない最小の数とするとき,もし qが合成数なら,

q=p’*r

となるq未満の素数p’が存在します。pとqの間には素数はありませんから,このp’はp以下の素数です。p以下の素数では既に篩われていますから,これは矛盾です。従ってqは素数です。ですから,

次に篩う素数は,今まで篩った素数より大きい,表に残っている最初の数

になります。


2.どの数の倍数を取り除くか

 素数pで篩う場合,2p,3p,...と取り除いていくわけですが,m<pの場合,mpはmの倍数ですから,既に取り除かれています。ですから,実際に取り除く必要があるのは,p*p,(p+1)*p,...となります。しかし,もしpが3以上なら,p+1は偶数で,(p+1)*pは既に取り除かれています。ですから,

pが3以上のとき,

p*p,(p+2)*p,(p+3)*p,(p+5)*p,...

とp以上の奇数倍を取り除けばよい

ということになります。このことから特に,n以下の素数表を作る場合,nの平方根以下の素数についてのみ篩えば良いことが分かります。


 この方法を使って例を挙げます。

計算例

 この方法で100以下の素数をすべて求めて見ましょう。

まず,2以上100以下の数の表を作ります。

  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

2で篩います。2より大きい2の倍数を除きます。除いた数を色を塗ります。

  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

次に2の次で最初に残っている3で篩います。この場合,3*3,5*3,7*3,...と奇数倍を取り除きます。

  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

次に3の次で最初に残っている5で篩います。この場合,5*5,7*5,7*5,...と奇数倍を取り除きます。

  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

次に5の次で最初に残っている7で篩います。この場合,7*7,9*7,11*7,...と奇数倍を取り除きます。

  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

7の次に残っている最初の数は11ですが,11*11が100を越えますので,これで終了です。ここで残っているのが素数になります。

プログラム例

 以上のことを行うプログラムを書いてみましょう。例えば1000までの素数表を作るとします。

まず,表は配列変数を使うのが自然です。Dim NT(1000) と宣言して使います。

自然数mが篩った結果取り除かれた場合,NT(m)=1 としましょう。まず,2で篩います。これは

For i=2 to 1000/2
   NT(i*2)=1
Next i 

と表されます。次にpを奇素数とするとき,pで篩います。これは

For i=p to 1000/p step 2
   NT(i*p)=1
Next i 

次に篩う素数を見つけるのは

p=p+1
While NT(p)=1:p=p+1:Wend

で得られます。


以上を纏めて一つのプログラムとすると次のようになります。簡単ですね。


Dim NT(1000)
For i=2 to 1000/2
   NT(i*2)=1
Next i
p=3
While p*p<=1000
   For i=p to 1000/p step 2
      NT(i*p)=1
   Next i
   p=p+1
   While NT(p)=1:p=p+1:Wend
Wend
For i=2 to 1000
   if NT(i)=0 then Print i
Next i
End

最後の For文は素数の表示です。

このプログラムを少し変更して,デモ用にした Ertsieve2.tbt はここにあります。またTiny Basic のSampleのなかにも Ertsieve.tbt もありますので参考にして下さい。