素数を求める二つの方法(ふるい)

エラトステネスのふるいと、サンダラムのふるいをつかって1000万以下(あとで１億以下)の素数を全てもとめます。

素数をもとめるだけでなく、両者の計算量を比較し、サンダラムのふるいがどれくらい効率をあげているか評価します。

サンダラムのふるいについて、Wikipediaなどの説明だと複雑そうにみえますが、要は２が素数であることを既知とし、最初から(2以外の)偶数は素数でないとしてふるいにかける方法です。

最初から、偶数がふるいから取り除かれているので、その分効率がよいというわけです。

効率についてここでは、メモリ使用量と、計算量（ここではふるいから消込した回数）で評価します。

効率評価

 

前提：まずは

最大10000000(1000万)までの素数を全て求める場合で効率を評価します。

MAX=10000000

と定数MAXを定義しておきます。

 

１．メモリ使用量の効率

（１）エラトステネスの場合

ふるいに必要な配列のサイズは、MAX-1です。

1を引いているのは、1が素数でないので、最初から除外しているためです。

（２）サンダラムの場合

ふるいに必要な配列のサイズは、(MAX-2)/2です。

2を引いているのは、1と2を最初から除外しているためです。また、奇数のみを考えるため半分の配列のサイズで用がたります。

（３）メモリ効率評価

仰々しくかくほどのものでもありませんが、サンダラムのほうがメモリ消費はエラトステネスにくらべて半分ですんでいます。地味ではありますが、コンピュータとしては、これは実にありがたいことです。逆にいうと、同じメモリでサンダラムは２倍の大きさの素数までもとめることができるということです。

 

２．計算量の効率

さて計算量についての評価です。これは、求める素数の上限MAXによって変化していきますが、MAX=1000万の場合で消し込む回数を求めました。

 

（１）エラトステネスの場合

エラトステネスの消し込んだ処理の回数＝23495188です。

ちなみに、求めた素数の個数= 664579

いまの６４ビットOSのマシンなら、あっというまにこの計算は終了します。

 

（２）サンダラムの場合

サンダラムの消し込んだ処理の回数＝9459882です。

求めた奇素数の個数は= 664578で、これに素数２を追加すれば、エラトステネスでもとめた個数と一致します。

 

（３）計算量評価

エラトステネスは、サンダラムに比べて2.48倍の計算量となっています。２倍以上の効率性がありました。これは、MAXが大きくなればなるほど、次第に2倍に近づいていくはずです。MAXの値が小さければ2.5倍以上の効率となっています。

 

使用したEXCELのプログラム

両者とも。VBAの配列に自然数を代入し、合成数のところを０に置き換え消込みしていきます。

 

エラトステネスの篩で素数を求めるバージョン

Const MAX = 10000000

‘素数リストを求める(Eratosthenes)
‘ついでに、消込処理の回数も数える
‘
Function set_prime_eratosthenes(s() As Long)
　u = UBound(s)
　’２以上の自然数をふるいにのせます
　For i = 0 To u: s(i) = i + 2: Next

　’合成数を消し込みます(0にする)
　For j = 0 To Int(Sqr(u))
　　If s(j) > 0 Then
　　　For i = j + s(j) To u Step s(j)
　　　　s(i) = 0 ‘消込処理
　　　　k = k + 1 ‘消込カウント
　　　Next
　　End If
　Next
　set_prime_eratosthenes = k
End Function

 

サンダラムの篩で素数を求めるバージョン

エラトステネスの篩版とほとんど同じです。偶数奇数の特性から、消し込むところも、結果的に同じになりました。

Const MAX = 10000000

‘素数リストを求める(Sundaram)
‘ついでに、消込処理の回数も数える
‘
Function set_prime_sundaram(s() As Long)
　u = UBound(s)

　’３以上の奇数をふるいにのせます
　　For i = 0 To u: s(i) = 2 * i + 3: Next

　’合成数を消し込みます(0にする)
　For j = 0 To Int(Sqr(u))
　　If s(j) > 0 Then
　　　For i = j + s(j) To u Step s(j)
　　　　s(i) = 0 ‘消込処理
　　　　k = k + 1 ‘消込カウント
　　　Next
　　End If
Next
set_prime_sundaram = k
End Function

 

それぞれの処理を呼び出して結果を表示するテストプログラム

長ったらしいので、サンダラムの篩バージョンのプログラムをテストする場合を掲載しておきます。

エラトステネスの篩バージョンでも、このプログラムを少し修正すれば使用可能です。

Sub test_set_prime_sundaram()
’Dim furui(MAX – 2) As Long　’エラトステネスの場合ここを修正
Dim furui((MAX – 2) / 2) As Long
Debug.Print

Debug.Print “Sundaram計算量=” & set_prime_sundaram(furui)

‘最後の10個の素数を出力し結果を確認する
c = 10
i = UBound(furui)
While c > 0 And i > 0
If furui(i) > 0 Then Debug.Print furui(i);: c = c – 1
i = i – 1
Wend

c = 0
For i = 0 To UBound(furui)
If furui(i) > 0 Then c = c + 1
Next
Debug.Print “求めた奇素数の個数=”; c
End Sub

 

 

参考(1億までもやってみた)

実は最初、EXCEL(VBA)で特に、チューンナップもしていないプログラムですから、1000万までの素数を全てもとめるにもそれなりの時間がかかるとふんでいました。

しかし、実行してみると数秒で処理が終わる(ただしファイルへの出力時間は含めない)ため、予定変更して１億までの素数を全て求めてみました。

ある程度メモリがあるマシンであれば、１億までの素数もそれほど時間をかけることなく求められます。これ以上になると、こんどは、扱える整数の上限の制限にひっかかるため、整数演算を64ビットに拡張するなどの工夫が必要になってきます。

 

下記は、１億までの素数を求めた計算量と、求めた素数の個数です。

Eratosthenesでの計算量=248304142
求めた素数の個数= 5761455

Sundaram計算量=100972367
求めた奇素数の個数= 5761454

効率　 248304142/100972367　≒　2.46 

サンダラム方式にすることで、２倍以上の効率の良さが発揮されていることがわかります。

 

テスト環境

テストで使用したマシンは、メモリ８Gで、CPU=i7-3770です。グラボは搭載していません。サンダラムの篩では10億までの素数を求める事がができました。10億でも1分以内で処理が終了しました。

 

[ad#foot]