LoginSignup
5

More than 5 years have passed since last update.

エラトステネスの篩 (Ruby 版)

Last updated at Posted at 2012-12-26

「エラトステネスの篩」の 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 秒でした。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
5