Project1

标题: 终于搞定了求100以内质数的写法了，但是问题来了。 [打印本页]
作者: px.凤翔九天    时间: 2010-12-13 23:10
标题: 终于搞定了求100以内质数的写法了，但是问题来了。
本帖最后由 px.凤翔九天 于 2010-12-13 23:30 编辑

我终于在钻研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
复制代码
作者: 六祈    时间: 2010-12-13 23:24
本帖最后由 六祈 于 2010-12-13 23:28 编辑

primers = []
for i in 2...100
   primers << i if primers.all?{|prime| i % primer != 0}
end
p primers
作者: 小湖    时间: 2010-12-13 23:25
求质数的算法不是循环除数，直到自己的开方么……
作者: px.凤翔九天    时间: 2010-12-13 23:27
本帖最后由 px.凤翔九天 于 2010-12-13 23:28 编辑

回复 小湖 的帖子

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


px.凤翔九天于2010-12-13 23:28补充以下内容：
看看你的写法，再看看我的..感到汗颜啊...继续修炼去
作者: 苏小脉    时间: 2010-12-13 23:30
本帖最后由 苏小脉 于 2010-12-13 23:30 编辑

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

额，苏小脉，你的编程和数学和我不是一个级别的...表示我的写法比较原始啊...谢谢楼上楼下各位的解释。表示5楼的连接中好方法好多啊...慢慢解剖学习...
作者: hysgdtc    时间: 2010-12-13 23:38
本帖最后由 hysgdtc 于 2010-12-13 23:45 编辑

可以用一种叫做 筛法 的算法， 理论上如果内存够用的话可以算任意有限长度的素数序列
伪代码：
定义数组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楼....
作者: 沙漠点灰    时间: 2010-12-14 17:48
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次

求更优解....



欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1