「エラトステネスの篩」の Ruby 版です。
「n 以下の素数を求める」という限定した条件下では、標準添付ライブラリの"prime.rb"よりかなり高速です。
prime_list.rb
# -*- coding: utf-8 -*-
# call-seq:
# prime_list(n) -> array
#
# * n 以下の素数を配列にして返す。
# * エラトステネスの篩 : 加算版
#
# === Example
# prime_list(20) => [2, 3, 5, 7, 11, 13, 17, 19]
#
def prime_list(n)
return [] if n < 2
return [2] if n == 2
limit = (n ** 0.5).to_i
arr = (1 .. n).step(2).to_a
arr[0] = 2
len = arr.size
i = 0
while true
i = i + 1
j = arr[i]
next unless j
break if j > limit
k = 2 * i * (i + 1)
while k < len
arr[k] = nil
k = k + j
end
end
arr.compact!
return arr
end
a = prime_list(100_0000)
Windows7, Intel Core i5, 2.4GHz の環境で、n = 1000000 の場合、約 0.1 秒でした。