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秒内就算出来了.
确定你知道自己要删除的是什么。
