D07 エラトステネスの篩

２からnまでの素数を調べていく有名な方法です。

小さい方から倍数を消していく，というごく単純な考え方ですが，アルゴリズムの練習として格好の題材でしょう。

このとき，nまで全部調べなくても，√n まで調べればよいことが知られています。

一般的な手順は

(1) 2からnまでの整数を書く。

(2) 2に丸をつけ、2より大きい2の倍数にバツを付ける。

(3) 以下は、まだ消されていない最小の整数に丸をつけ、その2倍以上の倍数にバツを付ける。

ですが，(3)のかわりに，

(3') 次の整数にバツが付いていなければ丸を付け、その2倍以上の倍数にバツを付ける。

とする方が多いでしょう．「まだ消されていない最小の整数」を探す方法が問題だからです。これを探すのに，つぎの数からバツがついているかどうか調べるのであれば(3')と同じです。

そこで，ひとまず(3')で進めますが，(1)〜(3')をそのとおりまじめにやるかどうか，それによってスクリプトが変わってくるでしょう。

というのは，最初から全部丸にしておいて，倍数をバツにしていっても同じだからです。さらに，(3')もまじめに判断しないで，全部やってしまうことも考えられます。

まずはその手抜きスクリプトです。なお，以下のスクリプトをコピーして実行するときは，各行の先頭に全角スペースが入っているのでこれを削除してください。

< その１ >

sieve(n):=(

res=apply(1..n,"〇");

res_1="×"; // １は素数ではない

repeat(floor(sqrt(n)),s,start->2,

m=floor(n/s); // sの倍数の個数

repeat(m-1,t,start->2,

res_(s*t)="×";

);

);

res;

);

試しに20まで結果を表示してみましょう。

あとで効率を調べるために処理回数（ループした回数）を記録しておきましょう。

sieve(n):=(

counter=0; // カウンタ

res=apply(1..n,"〇");

res_1="×"; // １は素数ではない

repeat(floor(sqrt(n)),s,start->2,

m=floor(n/s); // sの倍数の個数

repeat(m-1,t,start->2,

res_(s*t)="×";

counter=counter+1; // ここでカウント

);

);

println("処理回数＝"+counter); //カウンタ表示

res;

);

100までやると190回でした。

<その２>

sの倍数の個数を求めないで，repeat() の修飾子を用います。stopとstepです。

sieve(n):=(

counter=0; // カウンタ

res=apply(1..n,"〇");

res_1="×"; // １は素数ではない

repeat(floor(sqrt(n)),s,start->2,

repeat(n,t,start->2*s,stop->n,step->s,

res_t="×";

counter=counter+1; // ここでカウント

);

);

println("処理回数＝"+counter); //カウンタ表示

res;

);

100までの処理回数はその１とおなじく190回でした。

<その３>

(3') 次の整数にバツが付いていなければ丸を付け、その2倍以上の倍数にバツを付ける。

をまじめにやります。ただし，丸はすでについています。

sieve(n):=(

counter=0; // カウンタ

res=apply(1..n,"〇");

res_1="×"; // １は素数ではない

repeat(floor(sqrt(n)),s,start->2,

if(res_s!="×", // ここで判断

repeat(n,t,start->2*s,stop->n,step->s,

res_t="×";

counter=counter+1; // ここでカウント

);

);

);

println("処理回数＝"+counter); //カウンタ表示

res;

);

100までの処理回数は121回でした。