Ruby 实现 Eratosthenes筛法求素数 (性能相当于用定义求素数的C实现)

RubyInline, Making Making Things Faster Easier这篇文章用求素数这个例子来介绍用RubyInline在Ruby中混入C代码来提高性能.
然而"For Performance, Write it in C"只是选择之一,适当的选择算法有时来得更简单直接.
下面我用Eratosthenes筛法求素数的Ruby实现计算10000以内的素数,同样达到了上边引文里的0.X秒的性能.
如果用C来实现这个筛法,用链表而不是数组,性能可能还会提升很多.不过用上了Ruby就不会想回头了...

# 用Eratosthenes(埃拉托色尼,公元前三世纪的希腊天文学家、数学家和地理学家)筛
# 法求素数:创建一个数组,以下面的方式将某些位置以空标记:从位置2开始,将所有2的倍数
# 的位置标记为空,然后对2之后的素数3进行同样的操作这样就可以找到3之后未被标记的5, 
# 然后再将所有5的倍数记空,如此重复便可以找到数组中的所有素数。
# Sieve of Eratosthenes prime numbers Ruby 实现
def sieve(n)
  r=1..n # 得到数列
  a=r.to_a  # 将数列转化为数组
  c=0  
  i=0 # 数组下标从0开始,i+1对应数组成员2为素数
  (1..n).each do # 遍历整个数组    
    if a[i+=1]!=nil # i+1号数组成员如果没被当作合数划掉,执行下面的处理,同时移动数组下标指向下一个成员
      print "#{a[i]}," ;c+=1# 打印这个素数
      k=2 # 初始倍数     
      while a[i]*k <= n # 当素数的倍数小于既定范围时        
        # a[(i+1)*k-1]=nil # 相应的素数的整数倍合数被从数组中划去,对应数组成员标记为空
        # a.delete(a[i]*k) # 直接删去素数的倍数.执行性能差.
        a[a[i]*k-1]=nil # 相应的素数的整数倍合数被从数组中划去,对应数组成员标记为空 
        k+=1 # 加大倍数
      end
    end
  end
  puts "以上是#{n}以内的素数.共#{c}个."
end

puts"输入n"
n=gets.to_i  # 得到求值范围
if __FILE__ == $0
  t1 = Time.now
  sieve(n)  
  print t2 = Time.now - t1 ,"秒内完成"
end

-----------------------
07-4-16 edit
-----------------------
在 http://bohnsack.com/2006/02/13/cs-442-project-1-sieve-of-eratosthenes/ 里看到的:

max = Integer(ARGV.shift || 10000)
 
sieve = [nil, nil] + (2 .. max).to_a
 
(2 .. Math.sqrt(max)).each do |i|
  next unless sieve[i]
  (i*i).step(max, i) do |j|
    sieve[j] = nil
  end
end
 
puts sieve.compact.join(", ")

10000内素数0.0X秒内就算出来了.