ＰＣ上で奇素数を発生させるソフトはありますか？

ＰＣ上で奇素数を発生させるソフトはありますか？

パソコン上で奇素数： 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ・・・
を自動的に発生させるプログラム・ソフトは，何かありますか？

例えば，1000 という数値を指定して，ｐ＜1000　となる奇素数 ｐ の
すべてを数列　3, 5, 7, ・・・　のようにパソコン上で
発生させることは出来るでしょうか？

ご存知の方，教えて下さい．よろしくおねがいします．

No.4 ベストアンサー 回答者： kabaokaba 回答日時： 2010/04/27 21:42

昔Perlで書いたのを発掘．

perl prime.pl 10000 1000

とすると，最初から数えて10000個の素数のうち
1000未満のものを一気に出力します．
アルゴリズムとしては「エラトステネスの篩」を
少し効率化しています．


#prime.pl

use strict;
use warnings;

my $num =$ARGV[0];
my $upper =$ARGV[1];

sub primefactory{
my @primes=(2,3);
my $state=-1;
return sub{
$state++;
return $primes[$state] if $state==0 or $state==1;
my $prime_cand=$primes[-1]+2;
SIEVE:
foreach my $d (2 .. int(sqrt($prime_cand))+1){
if ($prime_cand % $d ==0){
$prime_cand++;
goto SIEVE;
}
}
@primes=(@primes,$prime_cand);
return $primes[-1];
}
}

my $x=primefactory();
foreach (1..$num){my $p=$x->();
if ($p<$upper) {print $p,"\n"}
else {last;}
}

この回答へのお礼

ご回答をありがとうございます.
早速，検討してみます．

お礼日時：2010/04/29 16:00

No.3 回答者： ziziwa1130 回答日時： 2010/04/27 20:39

ExcelのVBAでプログラムを組めばExcelのセルに表示できます。

この回答へのお礼

ご回答をありがとうございました．
Excel は使っておりませんので，残念ながら試せませんが，
今，Risa/Asir を使って検討中です．悪しからず．

お礼日時：2010/04/29 16:06

No.2 回答者： banakona 回答日時： 2010/04/27 20:35

＃１です。

大切なことを言い忘れました。割っていく数（３，５，７、・・・）は奇数でOKです。
素数にする必要はありません（素数を表示するプログラムに、素数が必要なんて
変ですしね！）。

この方法は結構ムダがある（例えば、３で割り切れなかった場合は、９で割り切れない
のは明らか）のですが、プログラムにする場合は、単純な方法の方が早い
場合があります。

実際、奇数の中から３の倍数をよけて割っていく素因数分解のプログラムを
組んだことがありますが、単純に奇数で割っていく方が計算が早かったです。

割られる方の数ｑも、高々１０００程度であれば、単純に奇数にするのをお勧めします。
３の倍数をよけたり５の倍数をよけたりしない方が、プログラムがシンプルになって
ミスもしにくくなります。

No.1 回答者： banakona 回答日時： 2010/04/27 20:15

できますよ。

原始的な方法ですが、素数か否かの判定をする奇数をｑとします。
奇数のみが対象なので、ｑを３，５，７、・・・と順番に割っていき、
割れ切れたら「素数でない」と判定します。どこまで割るかというと、
√ｑまでです。√ｑが整数でなければ、√ｑを超えない最大の奇数で
OKです。だから意外と早くこの判定は終わります。

例えば、ｑが１１９なら、√１１９＝１０．９・・・なので３，５，７，９
まで調べればいい。√ｑまで割って割り切れなければｑは素数です。
ｑを表示します。

ｑが素数か否か判定できたら、ｑを２増やし、また３から順に割っていきます。

以上をｑが９９９になるまで繰り返せば、ｐ＜1000　となる奇素数 ｐ の
すべてを数列　3, 5, 7, ・・・　のように表示できます。