エラトステネスの篩(ふるい)を少し改良したサンダラムの篩(ふるい)をつかって素数をもとめます。

サンダラムの篩をつかって奇素数を求めます。２を追加すれば素数リストになります。

エラトステネスの篩を使った方法より２倍ぐらい処理とメモリ使用に関して効率がよくなります。

サンダラムの篩

考え方はエラトステネスとそう変わりません。

なにが違うかといいますと、最初の２の倍数を最初から消したものとして考えることです。

奇数の素数だけ求めるのですが、奇数の合成数は奇数の素因数しか持ってないことに注目します。

なので、奇数の一覧表をつくっておいて、そこから、３の倍数、５の倍数、と奇数の倍数を消していきます。このあたりの消し方はエラトステネスの篩と同じような考えです。

サンダラムでは、偶数はすでに消されているとかんがえますから、奇数の奇数倍だけけして消していけばよいです。エラトステネスと比べて、最初の２で消し込む部分を省略することに加え、このあたりも改良されています。

そして、なんといっても、コンピュータでこの処理を行うと、メモリが半分で済むというメリットがあります。奇数だけ考えるので、考える数の数が半分ですむというわけですね。

実際に求めてみる

奇数だけ考えても同じようにできるのは、奇数×奇数＝奇数という性質があるからです。

エラトステネスで求めたように１００までの素数を求めてみます。

100までの奇数を列挙します(1は素数でないので省きました)。

3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35,37,39,41,43,45,47,49,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,83,85,87,89,91,93,95,97,99

3を素数確定とし、3の奇数倍の数(9,15,21,27,33,39,45,51,57,63,69,75,81,87,93,99)を消し込みます（ふるいにかけます）。

3,5,7,11,13,17,19,23,25,29,31,35,37,41,43,47,49,53,55,59,61,65,67,71,73,77,79,83,85,89,91,95,97

先頭の5を素数確定とし、5の奇数倍の数(15,25,35,55,65,75,85,95)を消し込みます。

3,5,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97

先頭の7を素数確定とし、7の奇数倍の数(21,35,49,63,77,91)を消し込みます。

3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

2を追加して、素数リスト「2,　3,　5,　7,　11,　13,　17,　19,　23,　29,　31,　37,　41,　43,　47,　53,　　59,　61,　67,　71,　73,　79,　83,　89,　97」が求められました。

エラトステネスに比べ、消し込む数（ふるいにかける数）が半分でできています。

しかも、最初に２の消し込みは不要で、最初のリストも半分ですんでいます。

つまり、作業領域が半分で、しかも計算量(消し込み量)は半分に改良されました。

プログラミングとしてのメモリ効率性

メモリ効率性というのは、コンピュータで計算するときの話です。プログラムを作る時には処理性能ももちろんですが、できるだけ少ないメモリで処理できるほうがすぐれているといえます。

コンピュータは計算するときにメモリを使用しますが、サンダラム方式はエラトステネス方式より半分のメモリで処理できるので節約されています。

計算を効率良くするために、奇数と自然数の対応をつくります。

考え方は奇数だけ考えるということになりますが、実際に計算するときには、奇数を自然数に対応させて効率化をはかります。すなわち、奇数は１引くとかならず偶数になるので２で割り切れます。

つまり、奇数2n+1とnを対応つけます。

対応例をすこし列挙しますと、

2n+1 → n　(奇数2n+1のかわりにnを使う)
1 → 0　(奇数1のかわりに0を使う)
3 → 1　(奇数3のかわりに1を使う)
5 → 2　(奇数5のかわりに2を使う)
7 → 3　(奇数7のかわりに3を使う)
9 → 4　(奇数9のかわりに4を使う)

です。

ややこしいですが、やっていることは簡単なことです。この対応によって、半分のメモリで処理ができるようになるわけです。しかも、扱う数の大きさも半分ですみます。

プログラミングへのヒント

具体的にプログラミングする時の処理について補足しておきます。

2n+1が合成数だとすると、2n+1=(2i+1)(2j+1)となる自然数i,jが存在します。

nについてとくと、n=2ij+i+jとなりますから、このようなnを篩にかけて消し込めばよいわけです。

また、\(\sqrt{2n+1}\gt 2i+1\),、\(\sqrt{2n+1}\gt 2j+1\)となるi,jについて調べればよいので、i,jの上限をここから抑えることができます。

たとえば、100までの素数を求める場合は、\(sqrt{100}=10 \ge 2i+1\)より、i､j=1,2,3,4の範囲で考えればよいことになります。

処理としては、1から[(100-1)/2]=49までのリストをつくり、そこから、

\(\left\{ 2ij+i+j|1 \le i,j, [(\sqrt{100}-1)/2] \right\}\)の集合の元をリストから消し込みます。

のこったリストを順に2倍して１を足せば奇素数のリストが出来上がります。2を付け加えれば素数リストになります。

 

(注)　記号[x]はxを超えない最大の整数を表す記号を表しています。

例：[(100-1)/2]=[49.5]=49、\([(\sqrt{100}-1)/2]\)=[9/2]=[4.5]=4 です。

実際のプログラム例（VBA)

後日エラトステネスのふるいとサンダラムのふるいをつかって素数を求めるプログラムを作り、両者のこうりつを評価してみました。こちらが結果です。

 

[ad#foot]