素数計算で言語の練習

id:shawshank99に、素数を計算するプログラムを書いてみてよ、といわれ、素数ってなんだっけ？と聞き返すという駄目さ極まるところを見せてしまったので、題材は素数計算。ものすごく基礎的でガッカリですが、やらない事は忘れるので、基礎からナメまわすことにしました。それに、RSA暗号では素数使いますしね。問題としては、入力された数nまでの素数を出力するプログラムを書いてみます。

このコードでは、愚直にn回ループ内に２〜n回ループですから、計算量はO(n^2)です。

FIRST_PRIME = 2
gets.to_i.times do |i|
    if (FIRST_PRIME...i).each{|n|
      if i%n == 0
        break(false)
      end
    } && i >= FIRST_PRIME
     puts i
  end
end

変な書き方のif式ですね。なんとeachを条件式に使っています。これは、eachに戻り値があるため可能な動作です。ブロックの中では、調べたい値を順に割り、その余りが０ならば、breakしています。ここでbreakに引数falseを渡す事で、breakしたときのeachの戻り値がfalseになります。さらにRubyではfalseとnil以外はすべて真という解釈をするので、すべて割り切れなかったとき、すなわち素数のとき、真が帰る仕組みになっています。
しかし、これではちょっと気持ち悪い書き方です。次のようにメソッドに分離した方がいいでしょう。

FIRST_PRIME = 2
def is_prime(i)
  (FIRST_PRIME...i).each do |n|
      break(false) if i%n == 0 
  end && i >= FIRST_PRIME
end
gets.to_i.times do |i|
  if is_prime(i) 
     puts i
  end
end

is_primeメソッドの中身、each~endの最後に&&がついててキモイという人もいるかもしれません。これは次のように１行であると見ると、多少分かり易いでしょう.rubyではメソッドの最後に書いた式がそのメソッドの戻り値になるため、これでtrue or falseが返ります。

def is_prime(i)
  (FIRST_PRIME...i).each {|n| break(false) if i%n == 0 } && i >= FIRST_PRIME
end

1-linerだとこうなります。

gets.to_i.times {|i|   if ((2...i).each{|n| break(false) if i%n == 0} && i>= 2) then puts i end}

ついでなので、Fixnumクラスにis_prime?メソッドを追加してみます。そうすると、数.is_prime?と呼ぶだけでtrueかfalseか分かって便利。

class Fixnum
  FIRST_PRIME = 2
  def is_prime?
    (FIRST_PRIME...self).each {|n| break(false) if self%n == 0 } && self >= FIRST_PRIME
  end
end

gets.to_i.times do |i|
     puts i if i.is_prime?
end 

puts 3.is_prime?  # これはtrue
puts 50.is_prime? # これはfalse

しかし、このままでは遅すぎて使い物になりません。6桁以上のnを入力するとすべて計算するのにひどく待たされます。素数の計算で有名なアルゴリズムに、エラトステネスの篩というものがあるので、実装してみましょう。

#受け取った数列の先頭を素数列に追加し、その倍数にあたる数を削除して返す。
def push_and_delete(nums, primes)
  num = nums.shift
  return nums.delete_if{|x| x%num == 0}, primes << num
end

nums, primes = push_and_delete((2..gets.to_i).to_a,[])

while(nums.max > (primes.max**2))
    nums, primes = push_and_delete(nums, primes)
end

puts (primes + nums).join(",")

愚直バージョンに比べて劇的に早くなりました。
勉強のために、愚直バージョンをCやJavaで実装してみることにします。