本文主要介绍python高效的素数判断算法。学算法的同学一定要看看。

高效素数判断算法

算法概述

这个算法集成了其他博主对基本素数算法的一些改进，包括以下三条规则：

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，可以从[2，sqrt(n)]判断素数，复杂度为sqrt(n)。

根据规则3，无论如何，2之后的偶数都可以判断(当n大于2时，当n除以2时，n不是素数，之后不需要判断，如果n除以2，之后的偶数不需要判断)。

假设n被2整除的概率等于n被2整除的概率，复杂度为sqrt(n)/4。

根据规则一，只需判断1/3的数，复杂度为sqrt(n)/12。

即时间复杂度为sqrt(n)/12。

计算过程中所做的假设和计算过程并没有那么严谨，这个结果仅供参考。

Python代码实现

定义初级法官：

#先把数字分成三类，小于等于1，大于1小于5，大于等于5。

#所有非整数都不是质数

如果不是isinstance(n，int):返回False

#小于1等于没有质数。

如果n=1:返回False

#大于1小于5

elif n==2或n==3:返回True

# 5或更高

elif n=5:

#先确定是否在6附近。

如果n % 6==5或n % 6==1:

#然后判断2是否能整除。

#如果可以，不是质数

如果n % 2==0:返回False

否则：

#不除2，直接跳过所有偶数。

对于范围(3，int(sqrt(n) 1)，2)中的I:

如果n % i==0:返回False

#经过筛选，是一个素数。

返回True

#不接近6不是质数

否则：返回False

以上是python高效的素数判断算法的细节。更多关于python的素数算法，请关注我们的其他相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。