终于搞定了求100以内质数的写法了，但是问题来了。

px.凤翔九天

我终于在钻研1个小时后搞定了显示100内质数的写法...（我的ruby书上的一道题...）这个算是我自己写的第一个脚本了吧（虽然用在游戏里极其鸡肋.........）觉得还是比较有成就感的。但是问题来了，这个写法只能算100以内的，200以内，300以内，10000以内甚至更多就不好使了...会漏掉一些项目，继续想就不会了，貌似需要比较纠结的迭代写法...虽然书上的题目就是100以内，但是进一步的话，希望各大高手教我一下。谢了
以下是我的写法，喜欢的拿去用（估计没人会用吧...因为太没用了）

1. #100以内质数求法
   
2.              #作者 px.凤翔九天
   
3. #说明：此脚本可以算出100以内的全部质数并返回到数组a
   
4. def assure(n)
   
5.   tempi=n.to_i
   
6.   if n==tempi
   
7.     return true
   
8.   else
   
9.     return false
   
10.   end
    
11. end
    
12. a=[2,3,5,7]
    
13. n=5
    
14. x=4.0
    
15. #无聊的定义了一个方法...
    
16. while x<=100.0
    
17.   #这里直接省掉了1到3，因为1到3不用计算机算吧...
    
18.   get=x/2
    
19.   if assure(get)==false
    
20.     get=x/3
    
21.     if assure(get)==false
    
22.       get=x/5
    
23.       if assure(get)==false
    
24.         get=x/7
    
25.         if assure(get)==false
    
26.           a[n]=x
    
27.           n+=1
    
28.         end
    
29.       end
    
30.     end
    
31.   end
    
32.   x+=1.0
    
33. end
    
34. a.compact!
    
35. a.collect!{|toi| toi.to_i}
    
36. p a
    

复制代码

六祈

primers = []
for i in 2...100
   primers << i if primers.all?{|prime| i % primer != 0}
end
p primers

小湖

求质数的算法不是循环除数，直到自己的开方么……

px.凤翔九天

回复 小湖 的帖子

开方？对，就是开方不能解决,,,
难道说每个做循环除以前的，开方另作处理？那样会变慢的吧.....


px.凤翔九天于2010-12-13 23:28补充以下内容：
看看你的写法，再看看我的..感到汗颜啊...继续修炼去

苏小脉

最容易实现的 naive 的算法是依次检测 2 ... sqrt(n) 是否都不为 n 的因数，再高级点的则只检测质因数，不过普遍认为对于　1000000 以内的质数用　Eratosthenes 筛法生成是比较好的。纯粹用来做数学研究的超大质数则通常是通过各种素性测试找到的，如针对梅森素数的 Lucas–Lehmer 素性检测法。
详见：
http://rpg.blue/forum.php?mod=vi ... =%E8%B4%A8%E6%95%B0

px.凤翔九天

额，苏小脉，你的编程和数学和我不是一个级别的...表示我的写法比较原始啊...谢谢楼上楼下各位的解释。表示5楼的连接中好方法好多啊...慢慢解剖学习...

hysgdtc

可以用一种叫做 筛法 的算法， 理论上如果内存够用的话可以算任意有限长度的素数序列
伪代码：
定义数组A[10000];
A=i;           //  数组序号等于数组内容
for(i=2~10000)
{
  如果A不等于0， 则 A[i*2], A[i*3], A[i*4]........ A[i*n] ( i*n<=10000 )全部赋值为0
}
这样所有数组里不是0的数就是素数了。
效率：同样是n^2的运算时间，没有用到除法和mod运算，时间会缩减一些。


hysgdtc于2010-12-13 23:48补充以下内容：
晕，我写贴的时候怎么没看到5楼....

沙漠点灰

lz的麻烦...2l的....是思路还是片段？运行错误...
一:
count = 0
array = []
for i in 2..100
  flag = true
  for ii in 2...i
    flag = false if i % ii == 0
    count += 1
  end
  array.push(i) if flag
end
p array
p "共循环#{count}次"

循环4851次
二:
count = 0
array = [2]
for i in 1...50
  i = i * 2 + 1
  flag = true
  for ii in 2..Math.sqrt(i).to_i
    if i % ii == 0
      flag = false
      break
    end
    count += 1
  end
  array.push(i) if flag
end
p array
p "共循环#{count}次"
循环162次

三：
count = 0
array = [2]
for i in 1...50
  i = i * 2 + 1
  flag = true
  for arr in array
    temp = Math.sqrt(i)
    if i % arr == 0
      flag = false
      break
    else
      if temp < arr
        break
      end
    end
    count += 1
  end
  array.push(i) if flag
end
p array
p "共循环#{count}次"
循环107次

求更优解....