如何优化这一段ruby代码以加快速度？

class PrimeGenerator
  def self.get_primes_between( x, y)
    sieve_array = Array.new(y) {|index|
      (index == 0 ? 0 : index+1)
    }

    position_when_we_can_stop_checking = Math.sqrt(y).to_i
    (2..position_when_we_can_stop_checking).each{|factor|
      sieve_array[(factor).. (y-1)].each{|number|
        sieve_array[number-1] = 0 if isMultipleOf(number, factor)
      }
    }

    sieve_array.select{|element| 
      ( (element != 0) && ( (x..y).include? element) )
    }
  end
  def self.isMultipleOf(x, y)
    return (x % y) == 0
  end
end

现在我这样做是为了“提交问题解决方案,因为你有时间杀死”网站.我选择ruby作为我的impl语言..然而我被宣布超时.
我做了一些基准测试

require 'benchmark'
Benchmark.bmbm do |x|
  x.report ("get primes") { PrimeGenerator.get_primes_between(10000, 100000)}
  end

ruby 1.9.1p0(2009-01-30修订版21907)[i386-mswin32]

L:\Gishu\Ruby>ruby prime_generator.rb
Rehearsal ----------------------------------------------
get primes  33.953000   0.047000  34.000000 ( 34.343750)
------------------------------------ total: 34.000000sec

                 user     system      total        real
get primes  33.735000   0.000000  33.735000 ( 33.843750)

ruby 1.8.6(2007-03-13 patchlevel 0)[i386-mswin32]

Rehearsal ----------------------------------------------
get primes  65.922000   0.000000  65.922000 ( 66.110000)
------------------------------------ total: 65.922000sec

                 user     system      total        real
get primes  67.359000   0.016000  67.375000 ( 67.656000)

所以我在C#2.0 / VS 2008中重新编写了这个东西 – >
722毫秒

那么现在这让我觉得我的实现是一个问题还是这种语言之间的差异？ (我对1.9 Ruby Ruby感到惊讶……直到我不得不将它与C#进行比较:)

更新：
原本是我的“put-eratosthenes-to-shame-adapt”:)消除不必要的循环迭代是主要的优化.如果有人对细节感兴趣,你可以阅读它here;反正这个问题太长了.

def sieve_to(n)
  s = (0..n).to_a
  s[0]=s[1]=nil
  s.each do |p|
    next unless p
    break if p * p > n
    (p*p).step(n, p) { |m| s[m] = nil }
  end
  s.compact
end

还有一些可能的加速,但我认为这是非常好的.

它们并不完全等效,所以你的10_000到1_000_000等于

sieve_to(1_000_000) - sieve_to(9_999)

或者近似的东西.

无论如何,在WinXP上,使用Ruby 1.8.6(和相当大的Xeon CPU),我得到了这个：

require 'benchmark'
Benchmark.bm(30) do |r|
  r.report("Mike") { a = sieve_to(10_000) - sieve_to(1_000) } 
  r.report("Gishu") { a = PrimeGenerator.get_primes_between( 1_000, 10_000) }
end

这使

user     system      total        real
Mike                            0.016000   0.000000   0.016000 (  0.016000)
Gishu                           1.641000   0.000000   1.641000 (  1.672000)

(我因为无聊等待而停止了100万箱的运行).

所以我会说这是你的算法.