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

chd114

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

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

除了以上，按照排除偶數的方式（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