蛋疼数学程序帝！质数算法。

亿万星辰

点评系统无法编辑。。。我淡定不能……{:nm_7:}

prime改成从 2 起的话，count还是要修改为0的，否则 4 就无法被剔除~

prime = (2..1000).to_a
count = 0
如此……{:nm_3:}

蛋糕

1. 当 要找质数时
   
2.    连接网络连接
   
3.    百度一下
   
4.    将第一个网页输出到输出框
   
5. 结束

复制代码

好罢……写完这个以后我真的蛋糕疼了……

枫起

表示我的最简单
http://baike.baidu.com/view/2868105.htm

紫苏

比较简单的是埃拉托斯特尼筛法：

BOUND = 1000000
primes = new bits[BOUND+1]
memset(primes, 1)
for i from 2 to BOUND
    if primes[i] then
        println(i)                // 输出质数
        j = i << 1
        while j < BOUND
            primes[j] = 0
            j += i
        end while
    end if
end for

还有一个阿特金筛法，据说是上述筛法的优化版，但没有试过
以上是找出某范围内所有质数的算法，但如果只是要确定某个数是不是质数的话，那直接用数学方法里的素性测试就行了

上帝的眼睛

1. MAX = 100
   
2. prime = []
   
3. for i in 0..MAX-2
   
4. prime[i] = i+2
   
5. end
   
6. i = 0
   
7. j = 2
   
8. while prime[i] != nil
   
9.   while prime[i]*j < MAX
   
10.     prime.delete(prime[i]*j)
    
11.     j += 1
    
12.   end
    
13.   i += 1
    
14.   j = 2
    
15. end
    
16. p prime

复制代码

好吧……这个是我自己写的……效率什么的无视就好……
看着这里的一对狂人们讨论，我真的好羡慕……

紫苏

II 和上帝的眼睛都用了动态数组的 delete，无形中就丢失效率了

另外还有个不是特别重要的问题：乘法运算需要多次移位，理论上来说是比加法要慢的，上面的乘法都可以由加法替换
1 * n = n
2 * n = n + n
....

IamI

II 和上帝的眼睛都用了动态数组的 delete，无形中就丢失效率了

另外还有个不是特别重要的问题：乘法运算需 ...
紫苏 发表于 2010-6-27 14:43

那么用数组标记法……输出的时候再全扫描一次？
另外2的次方也可以邪恶一下……

好吧……我没看见前面的东西……去研究下

紫苏

那么用数组标记法……输出的时候再全扫描一次？
另外2的次方也可以邪恶一下…… ...
IamI 发表于 2010-6-27 14:46

嗯，你俩写的本质上其实都是埃拉托斯特尼筛法，只不过你们用的是元素来存数值，而我用的是用第 n 位来表示 n 是否为质数。C++ STL 里有一个现成的容器类 bitset，可以当做位数组来用

另外上帝的眼睛给的链接里的算法还是没有脱离埃拉托斯特尼筛法的思想，刚搜了一下阿特金筛法，应该能比这个更快些：http://en.wikipedia.org/wiki/Sieve_of_Atkin

上帝的眼睛

1. MAX = 10000
   
2. t1 = Time.now
   
3. prime = []
   
4. kick = []
   
5. for i in 0..MAX-2
   
6. prime[i] = i+2
   
7. kick[i] = false
   
8. end
   
9. i = 0
   
10. j = 2
    
11. while prime[i] != nil
    
12.   while prime[i]*j < MAX
    
13.     #prime.delete(prime[i]*j)
    
14.     kick[prime[i]*j-2] = true
    
15.     j += 1
    
16.   end
    
17.   i += 1
    
18.   j = 2
    
19. end
    
20. prime.each{|v| puts v unless kick[v-2]}
    
21. t2 = Time.now
    
22. p t2-t1

复制代码

果然，这样很能提升效率么……（忽视最后一个……）

忽然想起来我买的一本书 《素数的音乐》……

紫苏

回复 上帝的眼睛 的帖子

这个其实自己做个测试也就知道了：

1. CASES = 5000
   
2. 
   
3. arr1 = (0...CASES).to_a
   
4. arr2 = (0...CASES).to_a
   
5. 
   
6. t = Time.now
   
7. CASES.times { |i| arr1.delete(i) }
   
8. p Time.now - t
   
9. 
   
10. 
    
11. t = Time.now
    
12. CASES.times { |i| arr2[i] }
    
13. p Time.now - t

复制代码

同样长度的数据，删除花的时间比随机访问多得多，从实现的角度来想，如果动态数组是乱序线性结构的话，那么删除元素就有一个线性搜索的过程，搜索到了该元素，还要让后面的元素前移， realloc 下内存大小；访问则是简单的数组首地址 + 偏移量
所以如果想要效率的话，删除元素必须慎用，除非你用的是散列表或是自我平衡/B/B+树之类的可以高效插入/删除的结构

另外附一个乘法和加法时间的比较：

1. CASES = 10000000
   
2. 
   
3. t = Time.now
   
4. for i in 1..CASES
   
5.   i + i
   
6. end
   
7. p Time.now - t
   
8. 
   
9. t = Time.now
   
10. for i in 1..CASES
    
11.   i * 2
    
12. end
    
13. p Time.now - t

复制代码