「エラトステネスの篩」の Ruby 版です。 「n 以下の素数を求める」という限定した条件下では、標準添付ライブラリの"prime.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 t
