Rubyと素数とエラトステネスの篩

最初篩1を
https://ja.wikipedia.org/wiki/エラトステネスの篩
を参考にRubyで書いた

エラトステネスの篩1

1) 2から、上限xまでの整数リストを作成しこれを探索リストとする。昇順。
2) 探索リストの左端から1つ取り出して削除し、素数リストに挿入。ここでの取り出しは常に素数
3) 探索リストから今取り出した素数の倍数(=素数で割り切れるもの)を削除して更新
4) 2で取り出す素数が上限xの平方根を超えている場合、もう残りの探索リストは素数だけなので、全部素数リストに挿入して終了

コメントでその後アドバイスをいただき2,3を追記

エラトステネスの篩2

コメントでのアドバイスを元に写経。篩1に加えて以下の考慮を加えている。
1) 偶数は2以外は合成数なのでその計算を省く。これで計算量が半分になる
2) 奇数はそれがたとえ素数としてもその奇数の階乗は合成数として省く

エラトステネスの篩3

Prime関数の素数生成。特に指定しない限りエラトステネス生成器を使う。

100万まで行くと、篩1は4分かかる。
2と3はほぼ変わらず、0.3secほど。

require 'benchmark'
require 'prime'

# エラトステネスの篩1

def primes1(max)
  # 上限数の平方根
  max_sqrt = Math.sqrt(max)
  # 素数リスト
  prime_list = Array.new
  # 探索リスト
  search_list=(2..max).to_a
  loop {
    primer = search_list.first
    # 探索リストから取り出した素数が、MAXの平方根を超えていたら
    # 残りの探索リストは素数だから
    # 探索を終了して素数リストに探索リストを全部入れる
    if primer > max_sqrt
      prime_list += search_list
      break
    else
      # 探索リストの先頭を1つ削り、素数リストに入れる
      prime_list << search_list.shift
    end
    # 探索リストの要素を今取り出した素数で割り切れるなら、倍数として削除して
    # 探索リストを更新
    search_list.delete_if{|num|
      num % primer == 0
    }
  }
  prime_list
end

# エラトステネスの篩2

def primes2(max)
  # 0からmaxまでの探索リスト
  # 利便性の点で添え字と値を一致させている
  # この探索リストから合成数を省いて(nilを代入)
  # 素数リストとしたい
  sieve = (0..max).to_a
  # maxの平方根まで素数を確かめて、その倍数を合成数として省けば
  # 平方根からmaxまでは素数しかない
  max_sqrt = Math.sqrt(max)
  # 素数ではない0と1をnilに
  sieve[0] = sieve[1] = nil
  # 偶数で2は素数であるため
  # 4以上の偶数を全てnil
  4.step(max,2){|num|
    sieve[num] = nil
  }
  # ある奇数の2乗に対してその奇数を足していく
  # 例) 3*3=9、その後9,12,15,18
  # それらは、その奇数(この場合は3)の倍数なので合成数とみなせる
  x = 3
  loop{
    if sieve[x]
      (x * x).step(max,x){|i|
        sieve[i] = nil
      }
    end
    x += 2
    break if x > max_sqrt
  }
  # nilを取り除く
  sieve.compact
end
result1 = Benchmark.realtime do
  primes1(100000)
end
result2 = Benchmark.realtime do
  primes2(100000)
end

# エラトステネスの篩3
result3 = Benchmark.realtime do
  Prime.each(100000).to_a
end


p "result1:#{result1}" #=> "result1:239.970237"
p "result2:#{result2}" #=> "result2:0.398498"
p "result3:#{result3}" #=> "result3:0.283707"