Willans 公式实现中的大数溢出问题与高效修正方案

本文解析基于 willans 公式的 python 素数生成器为何在计算第 8 个素数时触发 `overflowerror`，并提供数学原理驱动的数值稳定修正方法，避免阶乘转浮点导致的精度崩溃。

Willans 公式是一类利用三角函数和阶乘构造的“闭式”素数判定公式，其核心思想是：对正整数 $ j $，表达式
$$ \left\lfloor \cos^2\left(\pi \cdot \frac{(j-1)! + 1}{j}\right) \right\rfloor $$
当且仅当 $ j $ 为素数时值为 1（由威尔逊定理保证：$ j $ 是素数 ⇔ $ (j-1)! \equiv -1 \pmod{j} $，即 $ \frac{(j-1)!+1}{j} \in \mathbb{Z} $，故余弦值为 $ \cos(k\pi) = \pm 1 $，平方后为 1）；否则该值为 0。因此内层求和 sum 实际统计的是区间 $[1, i]$ 内的素数个数 $ \pi(i) $。

但原始代码存在致命数值缺陷：

factorial(j-1) 对 $ j \geq 20 $ 已达 $ 10^{18 }$ 量级，而 math.cos() 要求输入为 float，Python 中 int → float 转换在整数超过 $ 2^{53} $（约 $ 9 \times 10^{15} $）时丢失精度；
更严重的是，factorial(7!) = 5040!（当 j=5041 时出现）是一个拥有上万位的整数，远超 float 表示范围，直接触发 OverflowError。

关键误区在于：我们并不需要精确计算 $ \cos\left(\pi \cdot \frac{(j-1)! + 1}{j}\right) $ 的浮点值，而只需判断其是否等于 $ \pm 1 $ —— 这等价于判断 $ \frac{(j-1)! + 1}{j} $ 是否为整数。因此，应彻底规避浮点运算，改用模运算验证威尔逊条件：

def is_prime_wilson(j):
    if j < 2:
        return False
    if j == 2:
        return True
    if j % 2 == 0:
        return False
    # 使用威尔逊定理：j 是素数 ⇔ (j-1)! ≡ -1 (mod j)
    # 但直接算 (j-1)! mod j 仍可能慢；对小 j 可接受，大 j 建议换 Miller-Rabin
    prod = 1
    for k in range(2, j):
        prod = (prod * k) % j
    return prod == j - 1  # 即 (j-1)! ≡ -1 mod j

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

    count = 0
    candidate = 2
    while count < n:
        if is_prime_wilson(candidate):
            count += 1
            if count == n:
                return candidate
        candidate += 1
    return candidate

✅ 优势：完全整数运算，无浮点溢出风险；逻辑清晰，可验证性高。 ⚠️ 注意：is_prime_wilson 时间复杂度为 $ O(j^2) $，仅适用于教学或极小 $ n $（如 $ n \leq 20 $）。实际应用中应替换为 sympy.isprime() 或 Miller-Rabin 概率素性测试。

若坚持使用 Willans 公式框架（例如用于理论演示），可借助 decimal 模块控制精度，但仍无法解决阶乘过大导致的内存与性能瓶颈。更务实的做法是：承认 Willans 公式在计算数学中具有理论趣味性，但无实用价值——它用高复杂度换取了“公式化”表象，反而掩盖了素数分布的本质计算难度。

总结：OverflowError 根源是误将数论判定问题强行映射到浮点三角函数，违背了数值稳定性原则。正确路径是回归数论本质——用模运算替代浮点余弦，用算法思维替代公式幻觉。

# python # ai # 性能瓶颈 # cos # overflow # 三角函数

返回目录在线咨询

上一篇：python获取当前用户的主目录路径方法(推荐)
下一篇：合肥好的网站制作公司,合肥最大最好的交友网站是什么？

您的项目需求

*请认真填写需求信息，我们会在24小时内与您取得联系。

全网整合营销服务商

Willans 公式实现中的大数溢出问题与高效修正方案

您的项目需求