１．2〜Nの数をすべて「ふるい」に入れる．
２．「ふるい」の中で最小値を素数とする．図１の※．
３．今求めた素数の倍数をすべて「ふるい」からはずす．図１の斜線を引いた数．
４．２〜３をNまで繰り返し「ふるい」に残った（斜線を引かれなかった数）が素数である．
エラトステネスのふるい
キーワード：配列 ，For...Next ，If...EndIf ，Mod演算子 ，Sqr関数 ，Int関数 ，
素数とは，1と自分自身以外には約数をもたない数のことで，
2，3，5，7，11，・・・
などが素数である．1は素数ではない．
Nが素数であるか否かは，NがN以下の整数で割り切れるか否かを2まで繰り返し，割り切れるものがあ
った場合は，素数でないとしてループから抜ける．ループの最後までいっても割り切れる数がなかった
ら，その数は素数である．
なお，NをN/2以上の数で割っても割り切れることはないので，調べる開始の値はNではなくN/2からで
よいことは直感的にわかる．
数学的にはルートNからでよいことがわかっている．
例題１ 素数の判定
セルA1に記入されている値が素数か否かを判定し，その結果をセルA2に出力せよ．
Private Sub CommandButton1_Click() N = Range("A1").Value If N >= 2 Then SqrN = Sqr(N) Limit = Int(SqrN) For I = Limit To 2 Step -1 If (N Mod I) = 0 Then Exit For End If Next I If I = 1 Then Range("A2").Value = N & "は素数" Else Range("A2").Value = N & "は素数でない" End If End If End Sub
例題１では，Nが素数か否かを判定したが，同様の考え方を用いて2〜Nまでの全ての素数を求めるプロ
グラムも組めるはずである．
例題２ 2〜Nの全ての素数
セルA1に記入されている値までの全ての素数を求め，セルA2から横に10個ずつ出力せよ．つまり，
A2〜J2，A3〜J3,A4〜J4というふう出力する．
Private Sub CommandButton2_Click() Dim sosuu(10000) Num = Range("A1").Value M = 1 For N = 2 To Num SqrN = Sqr(N) Limit = Int(SqrN) For I = Limit To 2 Step -1 If N Mod I = 0 Then Exit For End If Next I If I = 1 Then sosuu(M) = N M = M + 1 End If Next N J = 1 K = 1 For I = 1 To M Cells(J + 1, K).Value = sosuu(I) K = K + 1 If K = 11 Then J = J + 1 K = 1 End If Next I End Sub
例題２の方法を用いてNまでの素数を求める場合，2〜Nまでの全ての値において素数であるか否かを
判定するので，非常に非効率的である．Nが小さい値のときは別段問題ないが，Nが大きな値になると処
理にかなりの時間がかかってしまう．
そこで，より効率よく素数を求める方法を紹介しよう．その方法とは，ギリシア時代から知られてい
るエラトステネスのふるいという方法である．名前に聞き覚えはないかもしれないが，その具体的な
方法は誰もが一度は目にしていると思う．
エラトステネスのふるい
Nまでの素数を求めるとする．まず，紙に２からNまでの値を全部書く．次に，2を残して2の倍数をす
べて消しゴムで消す．そこで残りの列の2の次を見ると3である．3は素数である．次に，3を残して，3
の倍数をすべて消す．残った列をみると，3の次は5である．4は2の倍数だから，前に消してある．そし
て，5を残して5の倍数を全部消す．このような手続を繰り返すと，素数だけが残ることになる．
このエラトステネスのふるいを用いてNまでの全ての素数を求めるプログラムを作っていく．
エラトステネスのふるいのアルゴリズムは以下のようになる．
１．2〜Nの数をすべて「ふるい」に入れる．
２．「ふるい」の中で最小値を素数とする．図１の※．
３．今求めた素数の倍数をすべて「ふるい」からはずす．図１の斜線を引いた数．
４．２〜３をNまで繰り返し「ふるい」に残った（斜線を引かれなかった数）が素数である．
図１ エラトステネスのふるい
さて実際にプログラムするにあたって，ふるいとして sosuu(2)〜sosuu(N) という配列を用意し，
2〜Nの数を「ふるい」に入れる操作をその配列要素を1にすることにし，「ふるい」からはずす操作を
その配列要素を0とすることにする．
例題３ エラトステネスのふるいを用いて 2 〜 N の全ての素数
エラトステネスのふるいを用いて，例題２と同様に2〜Nの全ての素数を求めよ．
Private Sub CommandButton1_Click() Dim sosuu(10000) Num = Range("A1").Value For I = 2 To Num sosuu(I) = 1 Next I SqrNum = Sqr(Num) Limit = Int(SqrNum) For I = 2 To Limit If sosuu(I) = 1 Then For J = 2 * I To Num If J Mod I = 0 Then sosuu(J) = 0 End If Next J End If Next I M = 1 L = 1 For I = 2 To Num If sosuu(I) = 1 Then Cells(M + 1, L).Value = I L = L + 1 If L = 11 Then M = M + 1 L = 1 End If End If Next I End Sub
正の整数を素数の積に分解することを素因数分解という．たとえば，126 = 2*3*3*7 と素因数分解
できる．
Nを素因数分解するアルゴリズムは以下の通りである．
１．まず，Nを2で割り切れなくなるまで繰り返し割っていく．その際，割り切れるたびに2を表示する．
２．割る数を3として同じことを繰り返し，以後，4，5，6，・・・と続けていく．
実際には素数についてだけ調べればよいのだが，素数表がないので手当たり次第に調べていく．しかし，素数
以外のもので割る場合は，それ以前にその数を素因数分解したときの素数（6なら2と3）ですでに割られている
ので，割り切れることはない．
３．割る数を A としたとき，ルートN ≧ A（N ≧ A×A）の間が２．を繰り返す条件である．
Nの値も割られるたびに小さくなっていく．
例題４ Nの素因数分解
セルA1の値を素因数分解し，その結果をセルA2から横に出力せよ．
Private Sub CommandButton1_Click()
N = Range("A1").Value
A = 2
J = 1
For I = 1 To N
If N < A * A Then
Exit For
End If
If N Mod A = 0 Then
Cells(2, J).Value = A
N = N / A
J = J + 1
Else
A = A + 1
End If
Next I
Cells(2, J).Value = N
End Sub