素数を求める方法。

質問

２から１０００までの、素数を求めるスクリプトを作るとしたら、あなたはどういうモノを作りますか？

回答No.3

BLUEPIXY · ベストアンサー

#エラトステネスの篩 by Perl
$max = 1000;#１０００までの素数
$prime[$count++]=2;
print "2\n";
N_LOOP:
for($n=3;$n<=$max;$n+=2){
for($i=0;$prime[$i]*$prime[$i] <= $n;$i++){
next N_LOOP if($n % $prime[$i] == 0);
}
$prime[$count++]=$n;
print "$n\n";
}

お礼

私も、求まりました♪
こんなにすっきりするんですねー。
２，３日試行錯誤して、どうにかなったのですが、これほど短くはなりませんでした。（ｗ；

これからも、自分の勉強もかねて、アルゴリズムっぽい質問をしたいと思います。感謝感謝♪
自前のスクリプトはなんか恥ずかしいので、アップしません。（笑
でも、いつかきちんとしたものを、アップしようかと。

回答No.2

akekou

エラトステネスの篩。
配列のデータ長が長くなるというなら、boolean型にするか、各配列の要素のbitを数字に当てはめて使うか、どちらかですね。
エラトステネスの篩を使ったことが無いようなので、int型で0,1を用いboolean型のように扱ってみるのが適切かと。

回答No.1

akirameta

エラトステネスの篩い。

補足

エラトステネスのふるい をそのままスクリプトにするとかえって難しくなりませんか？
一度、巨大な配列を作らないとダメだし、その後のふるい落とす処理も、私には面倒に感じます。
でも、逆にエラトステネスのふるいの方法でスクリプトを書いて頂けると、勉強になります。
Ｐｅｒｌでも、ＰＨＰでもＯＫです。（ｗ