Ruby 素数を出力する エラトステネスの篩(ふるい）

単純に考えてみる

問題

1から100の素数を全て出力してください。

解答

#素数を判定するメソッド
def check_prime(num)
  case num
  when 1 then
    false
  when 2 then
    true
  else
    (2..(num-1)).each do |index|
      if num % index == 0
        return false
      end
    end
    return true
  end
end

 #1から100までの素数の判定
 (1..100).each do |num|
   puts num if check_prime(num)
 end

もう少し真剣に考えみる

上記の書き方だと素数の値が大きくなってくると計算量かなり増えそう。。
それで改良策として
エラトステネスの篩(wikipedia)

指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。

手順としてはwikipediaには次のようにすればいいらしいと。

ステップ 1
探索リストに2からxまでの整数を昇順で入れる。
ステップ 2
探索リストの先頭の数を素数リストに移動し、その倍数を探索リストから篩い落とす。
ステップ 3
上記の篩い落とし操作を探索リストの先頭値がxの平方根に達するまで行う。
ステップ 4
探索リストに残った数を素数リストに移動して処理終了。

以下解答をご覧になりましたら、追記までご覧下さい

解答

include Math

#素数の配列を返すメソッド
def fetch_prime_list(max)
  list = (2..max).to_a
  prime_list = []
  sqrt = Math.sqrt(max).floor

  while val = list.shift
    prime_list << val
    if val > sqrt
      break
    end
    list.delete_if{|num| num % val == 0}
  end
  return prime_list.concat(list)
end

#配列の出力
p fetch_prime_list(100)

ポイント

• Array.shiftはなかなかに便利で、配列の先頭の値を消去してその値を返してくれる。
• Array.delete_ifは重要で、はじめに下記のように書いていてdelete_ifによってかなり高速化出来た。

  list.each do |num|
    list.delete(num) if num % val == 0
  end

比較する

どれくらいの違いが出たのか実験してみます。
benchmarkという標準ライブラリを用いて計算速度を比較します。
下記のように使用します。参考：Rubyで処理の時間計測方法

require 'benchmark'

result = Benchmark.realtime do
  # 処理
end
puts "処理概要 #{result}s"

実測

単純に考えたものをA、エラトステネスの篩で考えたものをBとします。
3回測ってみました。なお、差をわかりやすくするために「1から10000までの素数を出力する」時間で計測しました。

	A	B
1回目	0.5881432759342715s	0.016686114016920328s
2回目	0.5918690949911252s	0.014826877973973751s
3回目	0.57632252399344s	0.019242812995798886s

エラトステネスのほうがかなり速いですね！

追記

本記事でWikipediaのステップを参考に「エラトステネスの篩」の作成を試みたのですが、@yuki2006さんよりこれでは実行速度が速く、より正確な「エラトステネスの篩」の実装をご紹介頂いたので追記します。

include Math

#素数の配列を返すメソッド
def fetch_prime_list(max)
  table = Array.new(max + 1,true)
  prime_list = []

  (2..max).each do |num|
      if table[num] == true
        prime_list << num
      k = num * num
      while k <= max
        table[k] = false
        k += num
      end
    end
  end
  return prime_list
end

#配列を返すメソッド
p fetch_prime_list(10000)
end

なお、参考までにこのコードでの実行速度をCとすると

	A	B	C
1回目	0.5881432759342715s	0.016686114016920328s	0.003259235993027687s
2回目	0.5918690949911252s	0.014826877973973751s	0.004096289980225265s
3回目	0.57632252399344s	0.019242812995798886s	0.003389560035429895s

となり、実行速度が速いことが分かります。