北東北 LabVIEWユーザー会

キャンセル
次の結果を表示 
次の代わりに検索 
もしかして: 

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

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

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

 

PrimNums_2ways.png

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

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

 

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

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

 

0 件の賞賛
メッセージ1/7
2,397件の閲覧回数

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

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

 

PrimNums_3ways.png

 

 

0 件の賞賛
メッセージ2/7
2,350件の閲覧回数

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

 

 

PrimNums_3ways2.png

0 件の賞賛
メッセージ3/7
2,336件の閲覧回数

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

PrimeNums_3ways3.png

メッセージ4/7
2,303件の閲覧回数

わたしまさん、

ありがとうございます。

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

(Aは遅すぎるので削除しました)

 

PrimNums_3ways3Panel.png

 

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

 

0 件の賞賛
メッセージ5/7
2,294件の閲覧回数

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

素数をPとすると

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

ということですね。

 

すばらしい。

 

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

困ったものですね。

 

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

0 件の賞賛
メッセージ6/7
2,283件の閲覧回数

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

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

 

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

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

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


メッセージ7/7
2,276件の閲覧回数