Web系のこととかー。

Ruby プログラミング練習問題3「素数判定」

第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

う、うーん？
先生。まったく意味がわかりません。構文自体が謎…。ここら辺はちょっと構文調べてこよう。とりあえずまた次回。

§143 · 2月 16, 2010 · プログラミング_Ruby · · [Print]

Leave a Reply

←
→