・・・
を実現するプログラム例
#! ruby -Ks
def sh(a)
cn=0
for i in 1..a
if a%i==0 then
cn+=1
end
end
if cn==2 then
return 1
else
return 0
end
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
print "\n"
print "見つかった素数の個数は",cn,"個です。\n"
参考ダウンロード添付ファイル
さて、この原始的なプログラムを少しずつ改良していきましょう。
１３が素数であることを判定するのに、
１，２，３，４，５，６，７，８，９，１１，１２，１３で割り、
割り切ることの出来る数が２個だから、
素数であると判定していますが、
実は、２，３で割り切れれば素数と判定できます。
１では割り切れるに決まっていますから、
まず、１が除外されます。
では、４以上はどうして除外してよいのでしょうか。
約数の性質を考えて下さい。
例えば、１２の約数は
１，２，３，４，６，１２
です。
（１，１２）、（２，６）、（３，４）はどうなっていますか。
お互いに割ったときの商になっています。
（）内の数は相棒です。
とすれば、片割れだけを探せばよいですね。
１３の場合は（１，１３）が約数です。
ある数以下の約数が１しかないことが判明できれば、
それは素数です。そのある数とは何でしょうか。
１３に場合は、３です。
どうしてでしょうか。
４×４＝１６
３×３＝９
ですよね。
同じ数を２回かけることを２乗といいます。
同じ数を３回かける場合は、３乗ですし、
１０回なら１０乗です。
４の２乗が１６で、
３の２乗が９ですから、
２乗して１３になる数は、
３と４の間の数ということになります。
つまり、３．・・・・という小数です。
２乗して１３になる数を
という記号で表し、ルート１３と呼びます。
ですから、
＝３．・・・・というわけです。先ほどのある数以下のある数とは、
です。この数以下の整数ですから、３まで調べればよいのです。
どうしてルート以下の整数かといいますと、
９の約数を考えて下さい。
１，３，９
しかありません。
＝３ですね。（１，９）、（３，３）
３は３自身が相棒です。
つまり、相棒の片割れ（小さい方）はあるとしても、
ルートまでなのです。
＝３．・・・・ですから、約数が整数であるという約束に反しますから、
相棒の片割れ（小さい方）は
以下の整数で３までということになるのです。では、Rubyではどのようにしてルートｎを求めるのでしょうか。
＝n**(1/2.0)です。
（これは、ｎの１／２乗という意味です。
でも、難しいことは考えずに小学生の皆さんは、
n**(1/2.0)でｎのルートが求まるのだと理解して下さい。）
さて、改善しましょう。
改善効果を調べるために２つのバージョン共に時間計測をするようにしましょう。
旧バージョンの場合
新バージョンの場合
かなり速くなります。
第２話へ 第４話へ
