Ruby で素数判定をする

急に、自分が素数判定のプログラムを書けるのか気になったので書いた。

書けたんだけど、アルゴリズムの質が低い。3 以上の整数 n に対して、2 から n-1 までの数との剰余を算出して、それがすべて 0 でなければ素数、であると判定しているため計算回数が入力数に応じて尋常ではなくなる。

その反省を込めて、ベンチマークを取ってる。おそらく素数判定なんてもはや枯れていて、ちょっと検索すれば良いアルゴリズムが掲載されていると思う。

暇で気が向いた時が来れば、それらを採用して追記する。

追記

エラトステネスのふるいを書いた。100まででも実行速度がけっこう違っている。

prime_number.rb

require 'benchmark'

def prime_number?(n)
  if n < 2
    return false
  elsif n == 2
    return true
  end

  (2..n-1).each do |x|
    return false if n % x == 0
  end

  return true
end

result = Benchmark.realtime do
  limit = ARGV[0].to_i

  (2..limit).each do |n|
    p n if prime_number?(n)
  end
end

puts "処理時間： #{result}s"

def generate_prime_numbers(n)
  numbers = (2..n).to_a
  limit = Math.sqrt(n)
  prime_numbers = []

  while numbers[0] < limit
    prime_numbers << numbers.shift

    numbers.each do |i|
      numbers.delete(i) if i % prime_numbers.last == 0
    end
  end

  prime_numbers.concat(numbers)

  prime_numbers
end

n = 100
result = Benchmark.realtime do
  prime_numbers = generate_prime_numbers(n)
  p prime_numbers
end

puts "処理時間： #{result}s"

$ ruby app.rb 100
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
処理時間： 0.00035941600799560547s
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
処理時間： 0.0002646080101840198s