本文详解如何修复基于 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 公式在理论层面揭示了素数的“可公式化”可能性，但工程实现必须尊重数值现实。用可靠的素性判定替代脆弱的三角函数计算，是修复溢出、提升鲁棒性的根本之道。
