哪個演算法是判斷乙個數是否為素數的最簡單演算法？

1樓：青歌未晚

設定素數為N

1、2和3單獨判斷

2、不是素數的條件是可以被除了1和N整除，換句話說，就是有兩個小於自身的數相乘可以得到自身。按照√N為基準，這兩個約數一定是乙個比√N大乙個比√N少，所以直接找其中乙個存在不存在就可以，這樣需要遍歷的就只是從2到√N

3、按照6為推算，6x+2、6x+4為偶數，可以被整除。6x+3可以被3整除。剩下6x+1和6x+5，也就是說N要麼是6x+1，要麼是6x-1。其他所有都不是素數

從5開始到√N結束，步進為6去篩選約數，找不到，即為素數

def is_prime(number):

tmp = math.sqrt(number)

if (number == 2) | (number == 3):

return True

if (number % 6 != 1) & (number % 6 != 5):

return False

for i in range(5, int(tmp)+1, 6):

if (number % i == 0) | (number % (i + 2) == 0):

return False

return True

2樓：Omega

費馬小定理了解一下，如果乙個數n是素數，任取整數a屬於[2,n-1]，有（a^n）%n＝a。但有極少數不符合條件。

它的改進叫公尺勒羅蘋檢查，如果乙個數n是素數，任取整數a屬於[2，n-1]，必定(有a∧(n-1) )%n＝1。這個演算法已經廣泛用於計算機網路的加密中。而且相比費馬小定理，是一定不會出錯的。

3樓：小雨可白

最近正好發現乙個較為簡便的演算法，分享一下

定義對於任何自然數的結果只有

當且僅當為質數的時候，

其中是第項Fibonacci NumberFibonacci Sequence通項公式：

4樓：

遍歷N能否能被從2到sqrt(N)之間的素數整除。若不能則為素數。

比如判斷101是不是素數，只需要判斷101是否能被【2，10】之間的素數整除，即101是否能被2、3、5、7整除即可，如果不能，側101就是素數。

5樓：

補充：比如從1到n這麼多數，他們大體可以分成兩類，Fermat Witness，不是Fermat Witness

如果[1,...,n]存在Fermat Witness的話，n這個數一定不是質數

但是如果[1,...,n]不存在Fermat Witness的話， n這個數不一定是質數

因為實際上存在一些不是質數的數，他們沒有Fermat Witness

Miller-Rabin演算法裡用到了乙個strong witness的概念，算是乙個Fermat Witness的加強版：

如果n是質數的話，那麼在[1,...,n]之中是不存在strong witness

如果n不是質數，那麼[1,...,n]之中至少有(n-1)/2個strong witness

具體Miller-Rabin演算法的操作是，從[1,...,n]之中隨機取乙個，驗證被取出來的數是不是strong witness，如果是strong witness就返回「不是質數」，如果不是strong witness就返回「有可能是質數」。這個過程重複K次。

複雜度上，驗證strong witness是O(logn*logn)的，所以總共的複雜度是O(k*logn^2)，實際操作的時候大概試驗幾次左右就能出結果。

大致就記得這麼多了......

6樓：潘韜

這裡有詳細的說明

7樓：李陶冶

確定的演算法是AKS，05年被優化到log(n)^6，但複雜度還是比較高。憑概率的演算法是miller-rabin（建立在費馬小定理基礎上的），log(n)^2應該可以了。