高效素數判斷算法

算法概述

此算法將其他博主對基本素數算法的一些改進進行了整合，其中主要整合了如下三條規則：

1.大于3的素數一定在6的倍數前一個或后一個（如素數37在36的后面）

2.要判斷n是否為素數，只需要讓n從2開始，依次除到根號n即可

3.在進行“讓n從2開始，依次除到根號n”過程中，若n除以2的余數不為0，可以直接跳過[2, sqrt(n)]里面的所有偶數

博主語文素養不高，表達不是很準確，在后面會對這三條規則進行解釋。

規則詳解

1.大于3的素數一定在6的倍數前一個或后一個（如素數37在36的后面）

• 數學證明：

任意一個整數n可以表示為n = 6a + b ( 0 = b = 5, a >= 0 )，接下來依次講當n等于0到5的情況，以對此結論進行證明：

當n = 6a + 0 = 6a時，n有一個不為1及其本身的因數（素數判斷條件）6，此類數不為素數

當n = 6a + 2 = 2( 3a + 1 )時，n有一個不為1及其本身的因數（素數判斷條件）2，此類數不為素數

當n = 6a + 3 = 3( 2a + 1 )時，同上，有一因數3，此類數也不為素數

當n = 6a + 4 = 2( 3a + 2 )時，有一因數2， 此類數也不為素數

而當n = 6a + 1 或 n = 6a + 5時，不能絕對確定n是否為素數，需要考慮a的取值，顯然此時的數值n就是分布在6的倍數前一個或后一個

總結：大于3的素數一定分布在6的倍數前后

• 此規則可以直接對素數進行初步篩選，不符合此規則的數可直接判定為非素數，直接減少了2/3的運算量，效率提高肉眼可見
• 注意小于等于3的素數(2, 3)需要另外判斷

2.要判斷n是否為素數，只需要讓n從2開始，依次除到根號n即可

最基本的素數判斷方法是：讓n從2開始除，依次除到n - 1，如果每次除出來的結果余數皆不為0，那么此數n即為素數
實際上并不需要從除以[2, n - 1]區間的所有整數，只需除以[2, sqrt(n)]

3.在進行讓n除以[2, sqrt(n)]區間內的所有整數操作時，如果2不是n的一個因數，那么之后可以不判斷[2, sqrt(n)]區間的所有偶數

數學證明：當n/2除不盡時，n除以[2, sqrt(n)]區間內的所有偶數都除不盡

因此如果n不能將2除盡，那么之后的偶數一樣除不盡，可以直接不除
如果將2除盡了，n就不是素數，直接排除
如果沒有將2除盡，之后的計算量直接減半，肉眼可見的效率提升

算法時間復雜度復雜度

1.最基礎的算法：也就是讓n從2開始判斷，一直到n-1

若遇到的數是素數時，此時需要進行n-2次判斷
當遇到的不是素數時，要進行a（2an-2)次判斷
也就是說時間復雜度為n

2.改進后的算法：

根據規則二，判斷素數只要從[2，sqrt(n)]即可，此時復雜度為sqrt(n)
根據規則3，無論如何都可以不判斷2之后的偶數（當n大于2，當n除盡2時，n不為素數，之后不需要判斷，如果n除不盡2時，之后的偶數不要判斷）
假設n可以除盡2和不可以除盡2概率相等，那此時復雜度為sqrt(n)/4
根據規則一，只有1/3的數要進行判斷，此時復雜度為sqrt(n)/12
也就是說時間復雜度為sqrt(n)/12

在計算過程中做出的假設以及計算過程并不那么嚴謹，此結果僅供參考

Python代碼實現

def primeJudge(n):
 #先將數分為三類， 小于等于1，大于1小于5，和大于等于5
 #非整數統統不是素數
 if not isinstance(n, int): return False
 #小于1等于的都不是素數
 if n = 1: return False
 #大于1小于5
 elif n == 2 or n == 3: return True
 #大于等于5
 elif n >= 5:
  #先判斷是否在6的附近
  if n % 6 == 5 or n % 6 == 1:
   #再判斷是否可以將2除盡
   #可以的話不是素數
   if n % 2 == 0: return False
   else:
    #不可除盡2，直接跳過所有偶數
    for i in range(3, int(sqrt(n) + 1), 2):
     if n % i == 0: return False
    #經過篩選即為素數
    return True
  #不在6的附近不是素數
  else: return False

以上就是python高效的素數判斷算法的詳細內容，更多關于python素數算法的資料請關注腳本之家其它相關文章！