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<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 wrapsdef quick_power(a, b, p):"""求快速幂。ret = a^b%p 。Args:a: 底数。大于等于0并且是整数。b: 指数。大于等于0并且是整数。p: 模数。大于0并且是整数。Returns:返回结果。Raises:IOError: 无错误。"""a = a % pans = 1while b != 0:if b & 1:ans = (ans * a) % pb >>= 1a = (a * a) % preturn 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 resultreturn measure_time@timefn def is_prime_trial_division(num):"""判断是否是素数。试除法。Args:num: 大于等于2并且是整数。Returns:返回结果。true为素数；false是非素数。Raises:IOError: 无错误。"""if num <= 1:return Falseif num == 2 or num == 3 or num == 5 or num == 7:return Trueif num % 2 == 0:return Falsei = 3while num % i != 0:if i * i >= num:return Truei = i + 2return False@timefn def is_prime_fermat(num):"""判断是否是素数。费尔马素性测试法（Fermat primality test）可能会把合数误判为质数。Args:num: 大于等于2并且是整数。Returns:返回结果。true为素数；false是非素数。Raises:IOError: 无错误。"""if num <= 1:return Falseif num == 2 or num == 3 or num == 5 or num == 7:return Trueif num % 2 == 0:return Falsea = 2# a是[2,num-1]之间的随机数if quick_power(a, num - 1, num) == 1:return Trueelse: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)*ta = 2# 2, 325, 9375, 28178, 450775, 9780504, 1795265022s = 0t = num - 1num_1 = tif not (num % 2):return Falsewhile not (t & 1):t >>= 1s += 1k = quick_power(a, t, num)if k == 1:return Truej = 0while j < s:if k == num_1:return Truej += 1k = k * k % numreturn False@timefn def is_prime_comprehensive(num):"""判断是否是素数。综合算法:试除法+米勒拉宾素性检验可能会把合数误判为质数。Args:num: 大于等于2并且是整数。Returns:返回结果。true为素数；false是非素数。Raises:IOError: 无错误。"""if num <= 1:return Falseif 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 Trueif num % prime:if prime * prime >= num:return Trueelse: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算法，暂时没代码")执行结果如下：

文章插图
***
【2020-09-20:如何判断一个数是质数什么是质数】[评论](https://user.qzone.qq.com/3182319461/blog/1600556241)

2020-09-20:如何判断一个数是质数什么是质数

推荐阅读

晚熟蜂糖李几月份成熟？蜂糖李适合种植地区

问卷星审核要多久问卷星有提交时间吗

苹果airpods3上市时间苹果airpods3什么时间上市

b12对睡眠的作用维生素b12有安眠作用吗

什么是虚荣心虚荣心介绍

开瓶后的葡萄酒保鲜的窍门

白色会动的小白点是什么虫

2022年8月23日几点处暑

农视网福建漳州通报抑菌霜事件：涉事产品含激素线索已移送公安机关

事业单位计算机专业职称

麻酱烧饼的做法（增肥食谱）

台铃，省电跑更远！超能系列全国到店台铃掀年终热销风暴

北青网娱乐熊梓淇晒帅气照笑称“重拾偶像包袱”

一头鹿是什么牌子衣服

沙雅罗布麻茶是哪儿的特产吗？沙雅罗布麻茶介绍

财务报表构成应该如何比较

虾爆鳝背是哪儿的特产吗？虾爆鳝背介绍

养肝喝什么粥好？养肝粥食谱有哪些？

西瓜怎么吃才好吃西瓜怎么吃才好吃又简单

到底怎样锻炼才能练出肌肉？

2020-09-20:如何判断一个数是质数 什么是质数

推荐阅读

2020-09-20:如何判断一个数是质数什么是质数