如何降低给定数值范围内素数查找算法的计算复杂度

现有算法问题说明 #

你当前使用的是暴力枚举法，通过两层嵌套循环判断每个数是否为素数，时间复杂度为O(n²)，在输入数值较大时运行效率会明显下降。

可行优化方案 #

方案1：缩小内层循环上限至√i #

• 优化原理：如果正整数i存在大于√i的因数，那么必然存在一个与之对应的小于√i的因数，因此只需要遍历到√i即可完成素数判断，无需遍历到i-1。
• 时间复杂度：优化后为O(n√n)（即O(n^1.5)），明显优于原O(n²)复杂度。
• 优化后代码：

import math
x = int(input("Enter a natural number "))
prime = []
for i in range(2, x+1):
    is_prime = True
    # 内层循环仅遍历到√i
    for j in range(2, int(math.sqrt(i)) + 1):
        if i % j == 0:
            is_prime = False
            break
    if is_prime:
        prime.append(i)
print("The numbers are: ", prime)
print("There are", len(prime), "numbers")

方案2：使用埃拉托斯特尼筛法（Sieve of Eratosthenes） #

• 优化原理：直接通过标记法批量排除素数的倍数，不需要逐个判断每个数的因数。首先初始化一个长度为x+1的布尔数组，默认所有数值都是素数（标记为True），然后从最小的素数2开始，将所有2的倍数标记为非素数，再依次处理下一个未被标记的数（即下一个素数），直到遍历到√x为止，最终所有未被标记的数就是目标素数。
• 时间复杂度：O(n log log n)，性能远优于前两种方案，尤其适合处理大数值输入的场景。
• 实现代码：

x = int(input("Enter a natural number "))
if x < 2:
    prime = []
else:
    # 初始化标记数组，默认全为素数
    is_prime = [True] * (x + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(x ** 0.5) + 1):
        if is_prime[i]:
            # 标记i的所有倍数为非素数，从i²开始标记可以减少重复操作
            for j in range(i * i, x + 1, i):
                is_prime[j] = False
    # 收集所有标记为素数的数值
    prime = [i for i, val in enumerate(is_prime) if val]
print("The numbers are: ", prime)
print("There are", len(prime), "numbers")

效果验证 #

以上两种优化方案运行你的样本输入时，输出结果与原代码完全一致：

• 输入20时，输出素数列表为[2, 3, 5, 7, 11, 13, 17, 19]，共8个素数
• 输入50时，输出素数列表为[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]，共15个素数

内容的提问来源于stack exchange，提问作者Yalçın Cenik