エラトステネスの篩

今まで、Project Eulerの問題で素数を扱うときは、Prime.eachを多用してきたのですが、40000000までの素数を扱う問題で、これを列挙するだけでも、かなり時間を要することに気づきました。
そこで、定番のエラトステネスの篩を作って、Prime.eachと速度比較してみました。

prime_list.rb

• my_prime_listは、自作
• prime_listは、「エラトステネスの篩 #Ruby - Qiita」で紹介されていたものです。
• use_prime_libは、Prime.eachを用いたもの

# -*- coding: utf-8 -*-
require 'prime'
require 'benchmark'

def my_prime_list(n)
  arr = Array.new(n).fill(1)
  arr[0] = arr[1] = 0
  limit = Math.sqrt(n).to_i
  for i in 2..limit
    if arr[i] == 1
      2.upto(Float::INFINITY) {|j|
        if i * j < n
          arr[i * j] = 0
        else
          break
        end
      }
    end
  end
  prime_list = []
  arr.each_with_index {|e, i| prime_list << i if arr[i] == 1 }
  prime_list
end

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

def use_prime_lib(n)
  prime_list = []
  Prime.each {|pr|
    break if pr > n
    prime_list << pr
  }
  prime_list
end

MAX = 40_000_000
Benchmark.bm(15) do |x|
  x.report("My Eratosthenes") { p my_prime_list(MAX).size }
  x.report("Eratosthenes")    { p prime_list(MAX).size }
  x.report("Prime.each")      { p use_prime_lib(MAX).size }
end

実行結果

Prime.eachを用いる方法は10分以上かかっているのに対して、2番目のprime_list関数を用いる方法では7秒程度で実行できています。これほど実行速度に差があるとは思いませんでした。

$ ruby prime_list.rb
                      user     system      total        real
My Eratosthenes 2433654
 57.880000   0.340000  58.220000 ( 58.523879)
Eratosthenes    2433654
  7.380000   0.150000   7.530000 (  7.586200)
Prime.each      2433654
686.610000   1.910000 688.520000 (708.199233)