素数算法复杂度咨询及指定素数判定算法复杂度分析

首先来回答你第一个问题：素数相关算法的时间复杂度取决于具体实现类型，不同算法的效率差异很大，常见的几种如下：

• 基础试除法（单个数判定）：最直观的素数判定方法，时间复杂度为 O(√n)，因为只需要检查到n的平方根即可确定是否为素数。
• 埃拉托斯特尼筛法（批量生成素数）：经典的批量生成素数算法，时间复杂度是 O(n log log n)，效率远高于单个判定的试除法。
• 米勒-拉宾素性测试：概率性素数判定算法，时间复杂度为 O(k log³n)，其中k是测试轮数（轮数越高准确率越高）；对于小于2^64的整数，有固定测试用例可实现确定性判定，此时时间复杂度为 O(log n)。

接下来分析你给出的特定素数判定算法的时间复杂度：

先把你描述的算法整理为伪代码，更清晰直观：

输入: 整数 N ≥ 3
初始化 i = 2
循环:
    if N % i == 0:
        return 1  // 表示N不是素数
    if i == floor(sqrt(N)):
        return 0  // 表示N是素数
    i = i + 1

这个算法本质是优化后的试除法，它的时间复杂度是 O(√N)，原因如下：

• 最坏情况发生在N是素数时，此时循环会从i=2一直执行到i=floor(sqrt(N))，总循环次数为 floor(sqrt(N)) - 1，这个数量级等同于 √N。
• 如果N是合数，会在找到第一个能整除它的i时提前返回，平均情况的时间复杂度会比最坏情况低，但我们通常讨论的时间复杂度以最坏情况为准，因此整体复杂度为 O(√N)。

补充一个细节：当N是素数的平方（比如25）时，i会在等于5的时候触发N%i==0的条件返回1，不会走到i == floor(sqrt(N))的分支，所以算法逻辑是正确的。

内容的提问来源于stack exchange，提问作者Lamaman