整数N以下の素数列を求めるプログラム（エラストテレスのふるい）

[おおはし]

素数を求める単純な操作なので、いろいろなプログラム言語で書かれた例が紹介されています。

LabVIEWでは「LabVIEW Community Editionでプログラミングを楽しもう」の55ページでサンプルが提供されています。ループを使ったプログラミング例としてあまり複雑にならないようにと考えましたが、スピード重視ならばどんなプログラムになるか考えてみました。

オリジナルは、残ったすべての配列要素を素数で割り切れるかどうかチェックしているためループ回数が多くなっています。

スピードアップを図ったものは素数の倍数をチェックしているのでループ回数を少なくできています。

「整数N以下の素数列を求める」もっと速いプログラムを募集中!!

返信でVIを添付してください。

[おおはし]

Reshape Arrayを使って内側のWhileループを不要にしてみました。

Nが大きくなるとめちゃ遅い。

[おおはし]

内側のWhileループをForループに変更、ケースストラクチャ削除するとほんの少しスピードアップしました。ダイアグラムもスッキリしました。

[J.H.Watson]

Forループの回数が（置き換えのインデックスが無駄に回る）気になったのでちょっといじってみました。ウチのPCではNが少ないときにBが意外と速かったです。

[おおはし]

わたしまさん、

ありがとうございます。

私のPCで動く上限のNを入れて１０回平均で比較してみました。

（Aは遅すぎるので削除しました）

まだ読み解けていないですが、深遠なロジックみたいですね。

[おおはし]

ダイアグラムが理解できたような気がします。

素数をPとすると

「P*2からP*(P-1)まではすでに他の素数の倍数としてチェックされているので、P*P以上のPの倍数をチェックすればいい」

ということですね。

すばらしい。

もうひとつ気が付きました。私がプログラムAからBに変更するときにNの平方根を超えたら終了というのを忘れてしまっていたのですね。

困ったものですね。

ありがとうございました。

[J.H.Watson]

> 「P*2からP*(P-1)まではすでに他の素数の倍数としてチェックされているので、P*P以上のPの倍数をチェックすればいい」

はい。最初に気が付いたのはそれです。それでForループの回数を(P-1)回減らせました。

> Nの平方根を超えたら終了

最初はNの平方根と比較したのですが、逆に遅くなったりしました。

あてずっぽうでForループ回数が0以下で判定したら、ちょうど(N mod P)-(P-1)が「PがNの平方根を越えたら0以下になる」条件に合っていました。

---