Python高效素数判断算法：基于6k±1与根号优化的实现

算法概述

本算法整合了多位开发者对基础素数判定方法的改进思路，核心在于综合应用以下三条关键规则：

1. 所有大于3的素数，必然位于6的倍数的前一个数或后一个数位置（例如：素数37位于36之后）。

2. 判断整数n是否为素数时，只需尝试用从2开始到根号n之间的整数去除n即可。

3. 在执行“从2除到根号n”的过程中，若n不能被2整除（即余数不为0），则可直接跳过[2, sqrt(n)]区间内的所有偶数。

作者自谦表述可能不够严谨，下文将对上述三条规则进行详细解释。

规则详解

1. 所有大于3的素数，必然位于6的倍数的前一个数或后一个数位置（例如：素数37位于36之后）。

• 数学证明：

任意整数n均可表示为 n = 6a + b 的形式，其中 0 <= b <= 5 且 a >= 0。接下来依次分析b取0到5时n的性质，以验证该结论：

当 b = 0 时，n = 6a + 0 = 6a。此时n含有因数6（6不为1且不为n本身，除非n=6但6非素数），因此这类数不是素数。

当 b = 2 时，n = 6a + 2 = 2(3a + 1)。此时n含有因数2，因此这类数不是素数。

当 b = 3 时，n = 6a + 3 = 3(2a + 1)。同理，n含有因数3，因此这类数也不是素数。

当 b = 4 时，n = 6a + 4 = 2(3a + 2)。n含有因数2，因此这类数也不是素数。

而当 b = 1 或 b = 5 时，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整除，那么之后的偶数同样无法整除n，可直接跳过不判断。若n能被2整除，则n不是素数，直接排除。若n不能被2整除，后续计算量直接减半，效率提升明显。

算法时间复杂度分析

1. 最基础算法：即让n从2开始判断，一直持续到n-1。

若遇到的数是素数，此时需要进行n-2次判断。当遇到的不是素数时，需要进行a次判断（2 < a < n-2）。因此，其时间复杂度为O(n)。

2. 改进后的算法：

根据规则二，判断素数只需检查[2, sqrt(n)]区间，此时复杂度降为O(sqrt(n))。根据规则三，无论如何都可以不判断2之后的偶数（当n大于2时，若n能被2整除则非素数无需继续判断；若n不能被2整除，则后续偶数无需判断）。假设n能被2整除和不能被2整除的概率相等，此时复杂度约为O(sqrt(n)/4)。根据规则一，只有1/3的数需要进行判断，此时复杂度进一步降为O(sqrt(n)/12)。

上述计算过程中的假设及推导并不完全严谨，此结果仅供参考。

Python代码实现

def primeJudge(n):
 #先将数分为三类， 小于等于1，大于1小于5，和大于等于5
 #非整数统统不是素数
 if not isinstance(n, int): return False
 #小于1等于的都不是素数
 if n <= 1: return False
 #大于1小于5
 elif n == 2 or n == 3: return True
 #大于等于5
 elif n >= 5:
  #先判断是否在6的附近
  if n % 6 == 5 or n % 6 == 1:
   #再判断是否可以将2除尽
   #可以的话不是素数
   if n % 2 == 0: return False
   else:
    #不可除尽2，直接跳过所有偶数
    for i in range(3, int(sqrt(n) + 1), 2):
     if n % i == 0: return False
    #经过筛选即为素数
    return True
  #不在6的附近不是素数
  else: return False

以上就是Python高效素数判断算法的详细内容，更多关于Python素数算法的资料请关注本站其它相关文章！