福哥答案2020-09-20：#福大大架構師每日一題#
1.試除法。樸素素數篩，埃氏篩，歐拉篩和區間篩。代碼采用樸素素數篩。
2.費爾馬素性測試法法。費馬小定理：假如p是質數，a是整數，且a、p互質，那麼a的(p-1)次方除以p的餘數恒等于1，即：a^(p-1)≡1(mod p)。
3.米勒拉賓素性檢驗法。二次探測定理：如果p是一個素數，0<x<p,則方程x^2≡1(mod p)的解為x=1或x=p-1。
4.綜合法。試除法+米勒拉賓素性檢驗。
5.AKS算法。暫時無代碼。
因為用到了大整數，是以用python語言編寫。代碼如下：
# -*-coding:utf-8-*-
import math
import time
from functools import wraps
def 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 ans
def 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
@timefn
def 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
@timefn
def 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。用它們做 [公式] ， [公式] 以内不會出錯，我們使用這組數，就不用擔心運氣太差了。
@timefn
def 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
@timefn
def 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)