请求优化第n个素数查找代码，获取第10001个素数

首先你的原代码存在致命错误：循环内部的break语句会让循环仅执行一次，完全无法生成足够的素数，第一步要把这个break删掉。

修正后的基础版本 #

移除break后代码可正常运行，我们再做基础优化减少计算量：

def nthprime(n):
    if n == 1:
        return 2
    primes = [2]
    attempt = 3
    while len(primes) < n:
        is_prime = True
        sqrt_attempt = attempt ** 0.5
        # 仅检查到attempt的平方根即可，减少循环次数
        for prime in primes:
            if prime > sqrt_attempt:
                break
            if attempt % prime == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(attempt)
        attempt += 2
    return primes[-1]

print(nthprime(10001))

核心优化点 #

• 移除多余的break，让循环正常执行
• 增加n=1的边界判断，处理特殊情况
• 判断素数时仅检查到目标数的平方根：若一个数存在大于其平方根的因数，必然对应一个小于平方根的因数，无需遍历所有已生成素数
• 用普通for循环替代all()生成器表达式，发现非素数时提前终止循环，节省计算时间

更高效的方案：基于埃拉托斯特尼筛法 #

当n较大时（比如10001），可以先估算第n个素数的上限，再用筛法一次性生成范围内所有素数，直接取目标值。

第n个素数的近似上限公式（n≥6时）：n * (ln(n) + ln(ln(n)))，我们用这个公式确定筛的范围，确保覆盖目标素数：

import math

def nthprime_sieve(n):
    if n == 1:
        return 2
    # 估算第n个素数的上限
    if n < 6:
        upper = 15
    else:
        ln_n = math.log(n)
        ln_ln_n = math.log(ln_n)
        upper = int(n * (ln_n + ln_ln_n)) + 10  # 加10确保覆盖边界
    # 埃拉托斯特尼筛法生成素数
    sieve = [True] * (upper + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.isqrt(upper)) + 1):
        if sieve[i]:
            sieve[i*i : upper+1 : i] = [False]*len(sieve[i*i : upper+1 : i])
    # 收集素数并取第n个
    primes = [num for num, is_p in enumerate(sieve) if is_p]
    return primes[n-1]

print(nthprime_sieve(10001))

效率对比 #

• 基础修正版本适合小n场景，每次判断素数需遍历部分已生成素数，大n下耗时较长
• 筛法版本通过一次性生成范围内所有素数，大n场景下效率优势明显，计算第10001个素数的速度会快很多

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