新人练习脚本产物

亿万星辰

以下引用美兽于2007-5-25 19:28:54的发言：

这么几个字写了半个多小时,
使用的是古老的筛选法,
50000运行时间为0.0903s
在我机器上10s上限大约450万,
理论上仍有提升的空间,
有空再试吧......


M = 50000
t1 = Time.now
max = (M+1)/2
@date = Array.new(max)
for x in 1..max
@date[x] = (x << 1) - 1
end
m2 = max + 1
for i in 2..max
   next unless @date
   j = i + @date
   while j < m2
      @date[j] = nil
      j += @date
   end
end
@date.compact!   
t2 = Time.now
p t2-t1
p @date

看了一个多小时终于明白了....排除法~~~{/qiang}
如果通过一个数组来记录对应位数字是否为质数的真假值,最终根据这些真假值数组来重新生成一个真正的质数数组的话....

不过写完以后才发现这个更适合用做判断一个数是否为质数.....

我的机器上计算算不到4500000....  -v-|

1. def getzs(range)
   
2.   zs = Array.new(range,true)
   
3.   zs[1] = false
   
4.   t = Time.now
   
5.   r = Math.sqrt(range).ceil
   
6.   for i in 1..r
   
7.     if zs[i]
   
8.       j = 2 * i
   
9.       while j <= range
   
10.         zs[j] = false
    
11.         j += i
    
12.       end
    
13.     end
    
14.   end
    
15.   result = []
    
16.   for i in 1..range
    
17.     result.push(i) if zs[i]
    
18.   end
    
19.   p Time.now - t
    
20.   return result
    
21. end

复制代码

rpgdragon

好好學習!