關於判斷一個數是否為質數（素數）的腳本

chd114

一般來說是判斷n從2到n有沒有其他整數解
但是偶然搜到java的求質數（素數）的腳本

java中判断素数的六种方法 - CSDN博客
http://blog.csdn.net/kp_liu/article/details/37569507
該地址中判斷質數（素數）有6個循序漸進得來的方法，似乎後面的方法效率會更高一些

点击展开／收起

1. 1. 根据概念判断:如果一个正整数只有两个因子, 1和p，则称p为素数
   
2. 
   
3. 2. 改进, 去掉偶数的判断
   
4. 
   
5. 3. 进一步减少判断的范围
   
6. 定理: 如果n不是素数, 则n有满足1< d<=sqrt(n)的一个因子d.
   
7. 证明: 如果n不是素数, 则由定义n有一个因子d满足1< d< n.
   
8. 如果d大于sqrt(n), 则n/d是满足1< n/d<=sqrt(n)的一个因子.
   
9. 
   
10. 4. 剔除因子中的重复判断.
    
11. 定理: 如果n不是素数, 则n有满足1< d<=Math.sqrt(n)的一个"素数"因子d.
    
12. 证明: I1. 如果n不是素数, 则n有满足1< d<=Math.sqrt(n)的一个因子d.
    
13. I2. 如果d是素数, 则定理得证, 算法终止.
    
14. I3. 令n=d, 并转到步骤I1.
    
15. 由于不可能无限分解n的因子, 因此上述证明的算法最终会停止.
    
16. 
    
17. 5. 构造素数序列primes: 2, 3, 5, 7, ...
    
18. 由4的算法我们知道, 在素数序列已经被构造的情况下, 判断n是否为素数效率很高;
    
19. 
    
20. 6.(在素数表中)二分查找
    
21. Arrays.BinarySearch方法:
    
22. 该方法用于在指定数组中查找给定的值，采用二分法实现，所以要求传入的数组已经是排序了的。

复制代码

除了以上，按照排除偶數的方式（n%2==0 && n!=2），質數（素數）的特徵還有各位是0或5並且不是5（[0,5].include?(n.to_s[-1].to_i) && n!=5）則一定不是質數（素數）、所有位總和為3的倍數并且不是3（n.to_s.split("").collect{|i|n.to_s.to_i}.sum%3==0 && n!=3）則一定不是質數（素數）等雜七雜八的判斷（5和3的部分是在進入循環前就利用位上的數字做了判斷，不過好像用處不大？）

ruby中好像還有一個低效率而且有bug（字母進入直接true）的正則表達式用來找出質數

不討論那個低效率正則表達式

那在ruby中，用各種條件篩掉一部分理所當然的合數去尋找質數來提升效率而增加代碼量是值得的嗎？（我不太清楚加入各種條件以後能提升多少···）

uryeuf

啊呜先mark一下以后可能会用到（？）……
另外莫名想起当初学数学必修3的感觉……

chd114

uryeuf 发表于 2018-1-6 09:32
啊呜先mark一下以后可能会用到（？）……
另外莫名想起当初学数学必修3的感觉…… ...

(2..n).each{|i|return false if n%i==0}这个本来就是必修3上的做法
然后还有2个数的辗转相除法、进制转换等等···

SailCat

n%2 == 0
==>
n & 1 == 0
效率不是高一点半点儿

陆言儿

原答案大雾，一头栽进求N数以内的所有质数的坑里去了- -差点要打算讲一讲加法器乘法器除法器运算周期上去了- -
正确答案不值得，因为带来的时间提升量确实非常小，但是代码量同样小的不可以忽视我的话就会顺手写了= =
rpgmaker能涉及到的数就那么点，除非真的是在后台不断的堆栈运算，否则就那样吧。
--------------------------------------------------------------------
必然是值得的
--------------------------------------------------------------------

guoxiaomi

Miller-Rabin素性测试

http://blog.csdn.net/jokes000/article/details/7543612