高效素?cái)?shù)判斷算法

算法概述

此算法將其他博主對(duì)基本素?cái)?shù)算法的一些改進(jìn)進(jìn)行了整合，其中主要整合了如下三條規(guī)則：

1.大于3的素?cái)?shù)一定在6的倍數(shù)前一個(gè)或后一個(gè)（如素?cái)?shù)37在36的后面）

2.要判斷n是否為素?cái)?shù)，只需要讓n從2開(kāi)始，依次除到根號(hào)n即可

3.在進(jìn)行“讓n從2開(kāi)始，依次除到根號(hào)n”過(guò)程中，若n除以2的余數(shù)不為0，可以直接跳過(guò)[2, sqrt(n)]里面的所有偶數(shù)

博主語(yǔ)文素養(yǎng)不高，表達(dá)不是很準(zhǔn)確，在后面會(huì)對(duì)這三條規(guī)則進(jìn)行解釋。

規(guī)則詳解

1.大于3的素?cái)?shù)一定在6的倍數(shù)前一個(gè)或后一個(gè)（如素?cái)?shù)37在36的后面）

• 數(shù)學(xué)證明：

任意一個(gè)整數(shù)n可以表示為n = 6a + b ( 0 <= b <= 5, a >= 0 )，接下來(lái)依次講當(dāng)n等于0到5的情況，以對(duì)此結(jié)論進(jìn)行證明：

當(dāng)n = 6a + 0 = 6a時(shí)，n有一個(gè)不為1及其本身的因數(shù)（素?cái)?shù)判斷條件）6，此類數(shù)不為素?cái)?shù)

當(dāng)n = 6a + 2 = 2( 3a + 1 )時(shí)，n有一個(gè)不為1及其本身的因數(shù)（素?cái)?shù)判斷條件）2，此類數(shù)不為素?cái)?shù)

當(dāng)n = 6a + 3 = 3( 2a + 1 )時(shí)，同上，有一因數(shù)3，此類數(shù)也不為素?cái)?shù)

當(dāng)n = 6a + 4 = 2( 3a + 2 )時(shí)，有一因數(shù)2， 此類數(shù)也不為素?cái)?shù)

而當(dāng)n = 6a + 1 或 n = 6a + 5時(shí)，不能絕對(duì)確定n是否為素?cái)?shù)，需要考慮a的取值，顯然此時(shí)的數(shù)值n就是分布在6的倍數(shù)前一個(gè)或后一個(gè)

總結(jié)：大于3的素?cái)?shù)一定分布在6的倍數(shù)前后

• 此規(guī)則可以直接對(duì)素?cái)?shù)進(jìn)行初步篩選，不符合此規(guī)則的數(shù)可直接判定為非素?cái)?shù)，直接減少了2/3的運(yùn)算量，效率提高肉眼可見(jiàn)
• 注意小于等于3的素?cái)?shù)(2, 3)需要另外判斷

2.要判斷n是否為素?cái)?shù)，只需要讓n從2開(kāi)始，依次除到根號(hào)n即可

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

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

數(shù)學(xué)證明：當(dāng)n/2除不盡時(shí)，n除以[2, sqrt(n)]區(qū)間內(nèi)的所有偶數(shù)都除不盡

因此如果n不能將2除盡，那么之后的偶數(shù)一樣除不盡，可以直接不除
如果將2除盡了，n就不是素?cái)?shù)，直接排除
如果沒(méi)有將2除盡，之后的計(jì)算量直接減半，肉眼可見(jiàn)的效率提升

算法時(shí)間復(fù)雜度復(fù)雜度

1.最基礎(chǔ)的算法：也就是讓n從2開(kāi)始判斷，一直到n-1

若遇到的數(shù)是素?cái)?shù)時(shí)，此時(shí)需要進(jìn)行n-2次判斷
當(dāng)遇到的不是素?cái)?shù)時(shí)，要進(jìn)行a（2<a<n-2)次判斷
也就是說(shuō)時(shí)間復(fù)雜度為n

2.改進(jìn)后的算法：

根據(jù)規(guī)則二，判斷素?cái)?shù)只要從[2，sqrt(n)]即可，此時(shí)復(fù)雜度為sqrt(n)
根據(jù)規(guī)則3，無(wú)論如何都可以不判斷2之后的偶數(shù)（當(dāng)n大于2，當(dāng)n除盡2時(shí)，n不為素?cái)?shù)，之后不需要判斷，如果n除不盡2時(shí)，之后的偶數(shù)不要判斷）
假設(shè)n可以除盡2和不可以除盡2概率相等，那此時(shí)復(fù)雜度為sqrt(n)/4
根據(jù)規(guī)則一，只有1/3的數(shù)要進(jìn)行判斷，此時(shí)復(fù)雜度為sqrt(n)/12
也就是說(shuō)時(shí)間復(fù)雜度為sqrt(n)/12

在計(jì)算過(guò)程中做出的假設(shè)以及計(jì)算過(guò)程并不那么嚴(yán)謹(jǐn)，此結(jié)果僅供參考

Python代碼實(shí)現(xiàn)

def primeJudge(n):
 #先將數(shù)分為三類， 小于等于1，大于1小于5，和大于等于5
 #非整數(shù)統(tǒng)統(tǒng)不是素?cái)?shù)
 if not isinstance(n, int): return False
 #小于1等于的都不是素?cái)?shù)
 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除盡
   #可以的話不是素?cái)?shù)
   if n % 2 == 0: return False
   else:
    #不可除盡2，直接跳過(guò)所有偶數(shù)
    for i in range(3, int(sqrt(n) + 1), 2):
     if n % i == 0: return False
    #經(jīng)過(guò)篩選即為素?cái)?shù)
    return True
  #不在6的附近不是素?cái)?shù)
  else: return False

以上就是python高效的素?cái)?shù)判斷算法的詳細(xì)內(nèi)容，更多關(guān)于python素?cái)?shù)算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論