比较高效的质数判断算法高效的质数判断算法简介规则详细算法时间复杂度Python代码的实现
高效素数判断算法综述
该算法集成了其他博主对基本素数算法的一些改进，其中主要集成了以下三条规则：
大于3的素数一定在6的倍数之前或之后。 例如素数37在36后面。 要判断n是否是素数，只需从2开始，依次除以根号n即可。 在“从2开始n除以根号n”的过程中，如果n除以2的馀数不为0，则可以跳过[2，sqrt(n ) ]中的所有偶数语言博主
规则详细解大于3的素数一定在6的倍数的前面或后面。 例如素数37在36后面。 数学证明，任何一个整数n可以表示为n=6ab(0=b=5，a=0)，然后依次说明n等于0到5的情况来证明这个结论。
当n=6a 0=6a时，n有1和不是1的系数(素数检验条件) 6，这样的数不是素数
当n=6a2=2(3a1)时，n有1和非1本身的系数)素数判定条件) 2，这样的数不是素数
当n=6a3=3(2a1 )时，与上述相同，存在因数3，这种数量也不是素数
如果n=6a4=2(3a2)，则存在因数2，这种数量也不是素数
另一方面，显然，当n=6a 1或n=6a 5时，绝对不能确定n是否为素数，需要考虑a的取值，此时的数值n分布在6的倍数的前一个或后一个
总结：大于3的素数一定分布在6的倍数前后
此规则可以直接对素数进行初步筛选，不符合此规则的数可直接判定为非素数直接减少了2/3的运算量。 当效率提高时，需要明显注意的是，3以下的素数(2，3 )需要另外判断n是否是素数。 如果从2开始依次将n除以根号n，则最基本的素数的判断方法是将n从2开始除以，再依次除以n - 1，得到的结果
实际上，不必除以[2，n - 1]区间中的所有整数，只需除以[2，sqrt(n ) ]
执行n除以[2，sqrt[n]]区间内所有整数的操作时，如果2不是n的一个因子，然后不能被[2，sqrt[n]]区间内的所有偶数整除，意味着n不能被n/2整除，n是[
因此如果n不能将2除尽，那么之后的偶数一样除不尽，可以直接不除
如果能除尽2，则n不是素数，而是直接被排除
如果不被2整除，之后的计算量会直接减半，提高可见的效率
算法时间复杂度的最基本算法：即让n从2开始判断，遇到n-1的数为素数时，需要n-2次判断
遇到的不是素数时，进行a(2an-2 )次判断
也就是时间复杂度为n
改进后的算法：根据规则2，判断素数从[2，sqrt[n]]开始即可，此时复杂度为sqrt[n]
根据规则3，无论如何也可以不判断2之后的偶数。 (如果n大于2，n可以被2整除，则n不是素数，之后不需要判断。 如果n不能被2整除，则不判断之后的偶数) )。
假设n能被2整除的概率和不能被2整除的概率相等，则此时的复杂度为sqrt[n]/4
根据规则1，判断的只有1/3的整数，此时的复杂度为sqrt(n )/12
也就是时间复杂度为sqrt(n)/12
计算过程中的假设和计算过程不那么严格，此结果仅供参考
Python代码实现defprimejudge(n ) : # )首先将随机数分为三类，1以下、大于1且小于5以及5以上的非整数都不是素数if not isinstance(n ) n，而是int 小于等于1的都是素数if n=1: return False #大于1且5 elif n==2or n==3: return true #不小于5 elif n=5: #，首先， 判断在6附近是否有if n % 6==5 or n % 6==1: #，然后判断是否能被2整除，#如果可能的话，不能被素数IFN %2==0: returnfalseelse 3360 #整除偶数forIinrange(3 (跳过所有3的int(sqrt ) n )1)，2 ) : if n % i==0: return False # )的素数return True #不接近6是素数else 3360