2020-09-20：如何判斷一個數是質數？

福哥答案2020-09-20：#福大大架構師每日一題#

1。試除法。樸素素數篩，埃氏篩，尤拉篩和區間篩。程式碼採用樸素素數篩。

2。費爾馬素性測試法法。費馬小定理：假如p是質數，a是整數，且a、p互質，那麼a的（p-1）次方除以p的餘數恆等於1，即：a^（p-1）≡1（mod p）。

3。米勒拉賓素性檢驗法。二次探測定理：如果p是一個素數，0

4。綜合法。試除法+米勒拉賓素性檢驗。

5。AKS演算法。暫時無程式碼。

因為用到了大整數，所以用python語言編寫。程式碼如下：

# -*-coding：utf-8-*-import mathimport timefrom functools import wrapsdef quick_power（a， b， p）： “”“ 求快速冪。ret = a^b%p。 Args： a： 底數。大於等於0並且是整數。 b： 指數。大於等於0並且是整數。 p： 模數。大於0並且是整數。 Returns： 返回結果。 Raises： IOError： 無錯誤。 ”“” a = a % p ans = 1 while b ！= 0： if b & 1： ans = （ans * a） % p b >>= 1 a = （a * a） % p return ansdef timefn（fn）： “”“計算效能的修飾器”“” @wraps（fn） def measure_time（*args， **kwargs）： t1 = time。time（） result = fn（*args， **kwargs） t2 = time。time（） print（f“@timefn： {fn。__name__} took {t2 - t1： 。5f} s”） return result return measure_time@timefndef is_prime_trial_division（num）： “”“ 判斷是否是素數。試除法。 Args： num： 大於等於2並且是整數。 Returns： 返回結果。true為素數；false是非素數。 Raises： IOError： 無錯誤。 ”“” if num <= 1： return False if num == 2 or num == 3 or num == 5 or num == 7： return True if num % 2 == 0： return False i = 3 while num % i ！= 0： if i * i >= num： return True i = i + 2 return False@timefndef is_prime_fermat（num）： “”“ 判斷是否是素數。費爾馬素性測試法（Fermat primality test） 可能會把合數誤判為質數。 Args： num： 大於等於2並且是整數。 Returns： 返回結果。true為素數；false是非素數。 Raises： IOError： 無錯誤。 ”“” if num <= 1： return False if num == 2 or num == 3 or num == 5 or num == 7： return True if num % 2 == 0： return False a = 2 # a是［2，num-1］之間的隨機數 if quick_power（a， num - 1， num） == 1： return True else： return False# 米勒-拉賓素性檢驗是一種機率演算法，但是，Jim Sinclair發現了一組數：2， 325， 9375， 28178， 450775， 9780504， 1795265022。用它們做 ［公式］ ， ［公式］ 以內不會出錯，我們使用這組數，就不用擔心運氣太差了。@timefndef is_prime_miller_rabin（num）： “”“ 判斷是否是素數。米勒拉賓素性檢驗是一種機率演算法 可能會把合數誤判為質數。 Args： num： 大於等於2並且是整數。 Returns： 返回結果。true為素數；false是非素數。 Raises： IOError： 無錯誤。 ”“” # num=（2^s）*t a = 2 # 2， 325， 9375， 28178， 450775， 9780504， 1795265022 s = 0 t = num - 1 num_1 = t if not （num % 2）： return False while not （t & 1）： t >>= 1 s += 1 k = quick_power（a， t， num） if k == 1： return True j = 0 while j < s： if k == num_1： return True j += 1 k = k * k % num return False@timefndef is_prime_comprehensive（num）： “”“ 判斷是否是素數。綜合演算法：試除法+米勒拉賓素性檢驗 可能會把合數誤判為質數。 Args： num： 大於等於2並且是整數。 Returns： 返回結果。true為素數；false是非素數。 Raises： IOError： 無錯誤。 ”“” if num <= 1： return False if num & 1 == 0： return False # 100以內的質數表 primeList = ［3， 5， 7， 11， 13， 17， 19， 23， 29， 31， 37， 41， 43， 47， 53， 59， 61， 67， 71， 73， 79， 83， 89， 97］ # 質數表是否能整除 for prime in primeList： if num == prime： return True if num % prime： if prime * prime >= num： return True else： return False # 米勒拉賓素性檢驗 return is_prime_miller_rabin（num）if __name__ == “__main__”： print（is_prime_trial_division（12319）， “試除法”） print（“————————————”） print（is_prime_trial_division（561）， “試除法”） print（“————————————”） num = 1111111111111111111 # 質數 num = 561 # 合數 num = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F # 質數 num = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 # 質數 num = 2 ** 10000 + 111 # 合數 print（is_prime_fermat（num）， “費爾馬素性測試法”） print（“————————————”） print（is_prime_miller_rabin（num）， “米勒拉賓素性檢驗”） print（“————————————”） print（is_prime_comprehensive（num）， “綜合法”） print（“————————————”） print（“AKS演算法，暫時沒程式碼”）

執行結果如下：

***

［評論］（https：//user。qzone。qq。com/3182319461/blog/1600556241）