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

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

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

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

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

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

効率評価

 

前提:まずは

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

MAX=10000000

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

 

1.メモリ使用量の効率

(1)エラトステネスの場合

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

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

(2)サンダラムの場合

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

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

(3)メモリ効率評価

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

 

2.計算量の効率

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

 

(1)エラトステネスの場合

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

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

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

 

(2)サンダラムの場合

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

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

 

(3)計算量評価

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

 

使用したEXCELのプログラム

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

 

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

Const MAX = 10000000

‘素数リストを求める(Eratosthenes)
‘ついでに、消込処理の回数も数える

Function set_prime_eratosthenes(s() As Long)
 u = UBound(s)
 ’2以上の自然数をふるいにのせます
 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)

 ’3以上の奇数をふるいにのせます
  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万までの素数を全てもとめるにもそれなりの時間がかかるとふんでいました。

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

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

 

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

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

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

効率  248304142/100972367 ≒ 2.46 

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

 

テスト環境

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