新人练习脚本产物

Benavii

以下引用xgm于2007-5-22 21:13:02的发言：


PS:上限最好不要太大，RM默认10秒就挂，我的机器9秒才能算35000上限的……

估计着时间快要到的时候Graphics.update一下就可以不用挂吧{/fd}

亿万星辰

for i in $zs[$zs.size - 1] + 1..q #获取质数的范围
   for p in $zs #依次将质数列表里的数带入p
     if i % p != 0 #如果不能整除
       if p == $zs[$zs.size - 1] #如果p为目前指数列表的最后
         $zs[$zs.size] = i #将i写入
       end
     else #如果能整除
       break
     end
   end
   if Time.now - t1 > 9 #当程序快挂时刷新画面
     t1 = Time.now
     Graphics.update
   end

如果第二个循环里就有几万个数字的话,还运行不到判断这里,就已经挂了....


for i in $zs[$zs.size - 1] + 1..q #获取质数的范围
   for p in $zs #依次将质数列表里的数带入p
     Graphics.update
     if i % p != 0 #如果不能整除
       if p == $zs[$zs.size - 1] #如果p为目前指数列表的最后
         $zs[$zs.size] = i #将i写入
       end
     else #如果能整除
       break
     end
   end

也可以这样求稳,无非是慢一些,但绝对不会卡死....
你可以再做个显示进度的窗口,这样就不至于对着黑黑的屏幕发呆了......

美兽

求素数表啊.

很有挑战性啊.

明天试试优化效率,

在不建立表的情况LS几位搜索60万的速度是多少??

亿万星辰

1. $zs = [2]
   
2. def getzs(n)
   
3.   t = Time.now
   
4.   top = 1
   
5.   i = 3
   
6.   while i <= n
   
7.     q = Math.sqrt(i).to_i
   
8.     j = 0
   
9.     flag = true
   
10.     while $zs[j] <= q and j < top
    
11.       if i % $zs[j] == 0
    
12.         flag = false
    
13.         break
    
14.       end
    
15.       j += 1
    
16.     end
    
17.     if flag
    
18.       $zs.push(i)
    
19.       top += 1
    
20.     end
    
21.     i += 2
    
22.   end
    
23.   p Time.now - t
    
24.   return $zs
    
25. end
    
26. 
    
27. p getzs(50000)
    
28. 
    
29. exit

复制代码

印象里上学时好象最高效率是这么做的。。。。{/pz}
象这样算50000也大概就0.6秒左右{/hx}

美兽

这么几个字写了半个多小时,
使用的是古老的筛选法,
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

美兽

以下引用xgm于2007-5-25 21:00:23的发言：

我的算法太落后了,一个一个试....
前辈的方法都没看懂,正在研究中....
还有:  <<  是什么,帮助里没有,默认脚本里只有一处用到,不懂....

还有,请问初二数学知识能懂那两种算法吗

我那个是小学数学取质数表的方法......只是稍微加以改良,

<< 移位运算符,而数组字符串等对象也有这个,不过是方法,与数字的不一样,是用来加入对象的.