新新バージョン
を実現するプログラム例
#! ruby -Ks
hj=Time.now
def sh(a)
if a==1 then
return 0
end
if a==2 then
return 1
end
if a%2==0 then
return 0
end
b=a**(1/2.0)
for i in 3.step(b,2)
if a%i==0 then
return 0
end
end
return 1
end
cn=0
for i in 1..10000
if sh(i)==1 then
if i<10
print " ", i," "
else
if i<100 then
print " ", i," "
else
if i<1000 then
print " ", i," "
else
print i," "
end
end
end
cn+=1
if cn>1 && cn%20==0 then
print "\n"
end
end
end
ow=Time.now
print "\n"
print "見つかった素数の個数は",cn,"個です。\n"
print "素数探索時間は",ow-hj,"秒です。\n"
参考ダウンロード添付ファイル
旧バージョンの場合
新バージョンの場合
新新バージョン
今回は余り改善効果はありませんでした。
さらに、高速化を考えましょう。
新新バージョンでは、
例えば、４４３が素数であることを判定するために、
３，５，７，９，１１，１３，１５，１７，１９，２１
で割っていますが、
この中で９，１５，２１は不要です。
３の倍数でなければもちろん、
９，１５，２１の倍数ではありません。
３，５，７，１１，１３，１７，１９
で割れば良いのですが、
これって全部素数ですね。
そうです。
奇数ではなく、素数で割っていけばよいのです。
それまでに見つかった素数を配列に収納しておいて、
素数のみで割れば良いですね。
旧バージョンの場合
新バージョンの場合
新新バージョン
バージョン４の場合
第４話へ 第６話へ
