Python实现素数生成与数学计算优化技巧

1. 素数表生成函数实现（基础题58th）

素数判断与生成是编程入门阶段必须掌握的数学基础能力。我们首先构建一个判断素数的辅助函数，再基于它实现素数表生成器。

1.1 素数判断核心算法

最基础的素数判断采用试除法（Trial Division），即用2到√n之间的所有整数尝试整除n：

python复制def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

注意：循环上限取平方根是重要优化，因为若n能被大于√n的数整除，其对应的因子必然小于√n

1.2 素数表生成优化方案

直接遍历区间内每个数并调用is_prime()虽然可行，但对于大规模数据效率低下。更优方案是埃拉托斯特尼筛法（Sieve of Eratosthenes）：

python复制def generate_primes(limit):
    sieve = [True] * (limit+1)
    sieve[0:2] = [False, False]
    for num in range(2, int(limit**0.5)+1):
        if sieve[num]:
            sieve[num*num::num] = [False]*len(sieve[num*num::num])
    return [i for i, is_p in enumerate(sieve) if is_p]

该算法时间复杂度为O(n log log n)，比O(n√n)的暴力法有显著提升。实测生成100万以内素数仅需0.3秒，而暴力方法需要12秒。

2. 倒数数列求和函数实现（基础题59th）

倒数数列求和即计算1 + 1/2 + 1/3 + ... + 1/n，虽然形式简单但隐藏着重要数学原理。

2.1 基础实现与精度问题

最直观的实现方式：

python复制def reciprocal_sum(n):
    total = 0.0