第3回目のRubyプログラミング練習問題。今回は素数かどうかを調べる。
プログラミング練習問題3「素数判定」
与えられた数が素数かどうか調べる
あるいは与えられた数までの素数を列挙する
処理にかかった時間を計測しておくと、自分の技術向上に伴って処理時間が短くなっていくのがよくわかる
素数とは
素数自体について調べる余地はないと思っていたけど、念のためWikipediaさまを参照してみると1とその数自身以外に正の約数がない(つまり1とその数以外のどんな自然数によっても割り切れない)、1 より大きな自然数のこと。
ということだそうで。
とりあえずの回答
じゃあ、指定した数字が素数かどうかを調べるのを書いてみることにする。ぱっと思いついたのはやはり、2から指定した数まで全て列挙して割り算をしていくという力業。というかこれしか思いつかない。ならば簡単…ということで。
#!/usr/bin/ruby num = ARGV[0] flag = 0 2.upto(num.to_i - 1) do |i| over = num.to_i % i puts num + ' / ' + i.to_s + 'の余りは' + over.to_s + "\n" if over == 0 flag = 1 end end if flag == 0 puts num + 'は素数です' else puts num + 'は素数ではありません' end
実行結果
$./3_1.rb 5
5 / 2の余りは1
5 / 3の余りは2
5 / 4の余りは1
5は素数です
そもそも素数の判定方法がきちんと考えられていない…気もする。うーん。
まとめサイトに掲載されていた解答例
#!/usr/bin/ruby require 'mathn.rb' class PrimePredicater def initialize @prime = Prime.new @cache = [] end def prime?(x) extend_cache x if @cache.empty? || x > @cache.last @cache.include? x end private def extend_cache(lim) @prime.each do |x| break if x > lim @cache.push x end end end #使用例 ppred = PrimePredicater.new [1, 10, 2, 5, 7].each do |x| p ppred.prime?(x) end
う、うーん?
先生。まったく意味がわかりません。構文自体が謎…。ここら辺はちょっと構文調べてこよう。とりあえずまた次回。