如何修改Sundaram筛法函数，找到前n个素数时提前退出

要生成前n个素数，核心是找到一个足够紧凑的上限（即第n个素数的近似值），让Sundaram筛法无需处理远超目标的范围，同时确保能覆盖到第n个素数。

核心思路：用素数定理估算上限 #

素数定理给出第n个素数的近似公式，对于n≥6，这个估算值会略大于实际的第n个素数，完全能满足需求，比2^n这种极端宽松的上限高效太多：
p(n) ≈ n * ln(n) + n * ln(ln(n))

修改后的代码实现 #

先实现估算上限的函数，再调整原筛法逻辑，最后包装成生成前n个素数的函数：

import time
import math

def estimate_prime_upper_bound(n):
    if n == 1:
        return 2
    ln_n = math.log(n)
    ln_ln_n = math.log(ln_n)
    return int(n * (ln_n + ln_ln_n)) + 1  # 加1确保覆盖实际素数

def sieve_of_sundaram(limit):
    prime_list = [2]
    if limit < 2:
        return prime_list, 0
    n_new = (limit - 1) // 2
    marked = [0] * (n_new + 1)  # 索引从0到n_new，避免越界
    start_time = time.perf_counter_ns()
    
    for i in range(1, n_new + 1):
        j = i
        while True:
            idx = i + j + 2 * i * j
            if idx > n_new:
                break
            marked[idx] = 1
            j += 1
    
    for i in range(1, n_new + 1):
        if marked[i] == 0:
            prime_list.append(2 * i + 1)
    
    end_time = time.perf_counter_ns()
    overall_time = end_time - start_time
    return prime_list, overall_time

def get_first_n_primes(n):
    if n <= 0:
        return [], 0
    upper_bound = estimate_prime_upper_bound(n)
    # 极端情况下估算可能略小，加个保险循环（极少触发）
    while True:
        primes, duration = sieve_of_sundaram(upper_bound)
        if len(primes) >= n:
            return primes[:n], duration
        upper_bound += upper_bound // 10  # 增加10%上限

# 测试示例
if __name__ == "__main__":
    n = 5000
    primes, time_taken = get_first_n_primes(n)
    print(f"生成前{n}个素数耗时：{time_taken / 1e9:.6f}秒")
    print(f"第{n}个素数是：{primes[-1]}")

为什么不推荐动态扩展marked列表？ #

Sundaram筛法的标记逻辑依赖固定上限：每个非素数候选数i+j+2ij的计算基于预先确定的范围。动态扩展列表会导致：

• 重复执行标记循环，之前的i可能需要重新处理新扩展的范围
• 内存碎片和频繁扩容操作，大幅降低效率
  而素数定理估算的上限足够紧凑，额外处理的数极少，效率远高于动态扩展方案。

性能参考 #

生成5000个素数时，估算的上限约为53300，实际第5000个素数是48611，额外开销可以忽略，实际耗时会和你之前的0.0616秒相当甚至更快。

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