是否存在O(1)时间复杂度的素数判定算法？求高效素数检测方案

1. 是否存在时间复杂度为O(1)的素数判定算法？ #

目前不存在已知的精确素数判定算法能达到严格的O(1)时间复杂度。

核心原因是素数的分布尚未发现可直接计算的闭合式公式——尽管有威尔逊定理这类数学判定规则（当且仅当$(n-1)! \equiv -1 \pmod{n}$时，n为素数），但计算阶乘模n的操作本身复杂度极高，完全达不到O(1)的要求。

即便基于预计算素数表的查询看似是O(1)，但预计算过程需要消耗大量时间与空间，且无法覆盖所有可能的大数，因此这种方式不能算作真正意义上的O(1)算法。

2. 无需逐个检查目标数之前所有数字的高性能素数判定算法 #

这类算法确实存在，以下是几种主流方案：

优化版试除法 #

这是传统试除法的改进，彻底避免逐个检查所有前置数字：

• 先快速排除小于2的数、偶数（仅保留2作为例外）；
• 仅检查从3开始的奇数，且检查范围限定在目标数的平方根$\sqrt{n}$以内；
• 进阶版可只检查预计算好的素数集合，进一步减少检查次数。
  示例伪代码：

def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    max_divisor = int(n**0.5) + 1
    for d in range(3, max_divisor, 2):
        if n % d == 0:
            return False
    return True

米勒-拉宾素性检验（Miller-Rabin Test） #

这是一种高效的概率性算法（针对特定范围的数可转为确定性算法），基于费马小定理的变形，无需遍历大量数字：

• 通过选取若干个底数，对目标数进行一系列模运算测试；
• 实际场景中，选取2、3、5、7、11这类少量底数，就能以极高准确率判定素数；
• 时间复杂度远低于试除法，是大素数判定的首选方案之一。

AKS素性检验 #

这是首个被证明的确定性多项式时间素数判定算法，基于数论中的多项式恒等式，完全无需逐个检查前置数字：

• 时间复杂度为$O(\log^6 n)$，对大数判定的性能远超传统试除法；
• 理论意义重大，仅因常数因子较大，实际应用中不如米勒-拉宾普及，但完全满足“无需逐个检查所有前置数字”的要求。

内容的提问来源于stack exchange，提问作者M. A. Haikal