Willans 公式实现素数生成时的数值溢出修复教程

本文详解如何修复基于 willans 公式（利用三角函数与阶乘判断素数）的 python 实现中因阶乘过大导致 `overflowerror: int too large to convert to float` 的核心问题，并提供可运行的数值稳定替代方案。

Willans 公式是一类基于初等函数（如三角函数、取整、阶乘）构造的“显式”素数公式，其理论形式优美，但在实际编程中极易因数值精度与范围限制而失效。你遇到的错误：

OverflowError: int too large to convert to float

根本原因在于：当 j 增大（例如 j ≥ 18），factorial(j - 1) 迅速超出 Python float 的表示范围（约 10^308），而 cos() 函数强制要求浮点输入——即使你调用 math.cos() 传入一个超大整数除法结果，Python 仍需先将其转为 float，从而触发溢出。

⚠️ 关键误区澄清：

• decimal.Decimal 无法解决此问题，因为 math.cos() 不接受 Decimal 类型，且 cos() 本身是 math 模块的 C 实现，只支持 float；
• 单纯“减去 2π 的整数倍”（即模 2π 归约）在浮点下依然无效：对超大数 x 计算 x % (2*pi) 会先尝试将 x 转为 float，早已溢出。

✅ 正确思路：避免计算超大数的三角函数，转而利用数论性质直接判定 cos²(π·(k)/j) 是否 ≈ 1 或 0。

根据威尔逊定理（Wilson’s Theorem）：

j 是素数 ⇔ (j−1)! ≡ −1 (mod j) ⇔ (j−1)! + 1 ≡ 0 (mod j) ⇔ j ∣ ((j−1)! + 1)

因此，((j−1)! + 1) / j 是整数 当且仅当 j 是素数（或 j = 1，需单独处理）。此时：

• 若 j 是素数 ⇒ ((j−1)! + 1)/j ∈ ℤ ⇒ π × 整数 ⇒ cos(π × 整数) = ±1 ⇒ cos² = 1；
• 若 j 是合数且 j > 4 ⇒ (j−1)! ≡ 0 (mod j) ⇒ ((j−1)! + 1)/j 非整数 ⇒ cos²
• 特殊小值（j=1,4）需手动校验。

于是，原式中关键项：

floor(cos(π * (factorial(j-1)+1) / j) ** 2)

逻辑等价于：

• 返回 1 当且仅当 j 是素数（或 j=1）；
• 返回 0 否则（j≥2 合数时，cos² 值严格小于 1，floor 后为 0）。

因此，我们完全无需计算 cos，只需用高效素数判定替代即可！以下是修复后的稳定实现（使用试除法，兼顾简洁与实用性）：

def is_prime(x):
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    i = 3
    while i * i <= x:
        if x % i == 0:
            return False
        i += 2
    return True

def nth_prime(n):
    if not (isinstance(n, int) and n > 0):
        raise ValueError("n must be a positive integer")

    # Willans 公式简化版：count primes ≤ m until we find the nth
    # Note: Original Willans uses double sum; we replace inner sum with prime count π(m)
    def prime_count(m):
        return sum(1 for j in range(2, m + 1) if is_prime(j))

    # Binary search for smallest m such that π(m) >= n
    lo, hi = 2, max(10, n * (n.bit_length() + 1))  # rough upper bound
    while lo < hi:
        mid = (lo + hi) // 2
        if prime_count(mid) >= n:
            hi = mid
        else:
            lo = mid + 1
    return lo

# 测试
print(nth_prime(1))   # 2
print(nth_prime(8))   # 19
print(nth_prime(25))  # 97

? 为什么这更优？

• ✅ 无溢出风险：不计算大阶乘，不调用 cos/pi；
• ✅ 时间可控：对 n=8，最大测试 m≈30，prime_count(30) 仅检查 28 个数；
• ✅ 可扩展：配合 Miller-Rabin 等算法，可轻松支持 n=1000+；
• ✅ 符合原意：本质仍是 Willans 公式所依赖的威尔逊定理逻辑，只是用计算友好的方式实现。

? 进阶提示：若坚持使用纯数学表达式（如用于教学演示），可用 sympy 的符号计算规避浮点——但性能极低，仅作验证：

from sympy import cos, pi, factorial, floor, S
# 注意：sympy.cos 可处理大整数符号运算，但速度慢，不推荐生产使用

总结：Willans 公式在理论层面揭示了素数的“可公式化”可能性，但工程实现必须尊重数值现实。用可靠的素性判定替代脆弱的三角函数计算，是修复溢出、提升鲁棒性的根本之道。