Willans 公式生成第 n 个素数的 Python 实现与溢出修复指南_网络技术

本文详解 willans 公式在 python 中的实际应用，分析 `factorial(j-1)` 导致的浮点溢出根本原因，并提供基于模 2π 化简、高精度计算和数学优化的完整解决方案，使公式可稳定计算至第 10 个素数及以上。

Willans 公式是一类纯数学构造的素数生成公式，其核心思想是利用三角函数（如余弦）的取值特性编码 Wilson 定理：当且仅当 $ j $ 是素数时，$ (j-1)! \equiv -1 \pmod{j} $，即 $ \frac{(j-1)! + 1}{j} $ 为整数，此时 $ \cos\left(\pi \cdot \frac{(j-1)! + 1}{j}\right) = \pm 1 $，其平方为 1；否则结果落在 $ (-1,1) $ 内，平方后小于 1，向下取整为 0。因此内层求和 sum 实际统计了区间 $[1,i]$ 内的素数个数 $ \pi(i) $。

但原始实现存在严重缺陷：当 j 增大（例如 $ j \geq 18 $），factorial(j-1) 迅速突破 $10^{15}$ 量级，而 math.cos() 要求输入为 float——Python float 仅能精确表示约 $2^{53} \approx 9 \times 10^{15}$ 以内的整数，超出后转 float 即丢失精度，且对极大数取模 2π 时，浮点误差被急剧放大，最终触发 OverflowError 或返回无意义值。

✅ 正确解法不是强行用 Decimal 替换 float（math.cos 不支持 Decimal），而是数学化简：利用余弦函数周期性
$$ \cos(\pi x) = \cos\big(\pi \cdot (x \bmod 2)\big) $$
因为 $ \cos(\theta) = \cos(\theta \bmod 2\pi) $，而此处角度为 $ \pi x $，故只需将 $ x = \frac{(j-1)! + 1}{j} $ 对 2 取模，即计算 $ x \bmod 2 $。注意：$ x $ 是有理数，但 $ (j-1)! + 1 $ 除以 $ j $ 的整数部分不影响模 2 结果——关键在于判断该商是奇数还是偶数（因 $ \cos(k\pi) = (-1)^k $）。

更进一步，由 Wilson 定理：

若 $ j $ 是素数，则 $ (j-1)! \equiv -1 \pmod{j} \Rightarrow (j-1)! + 1 \equiv 0 \pmod{j} $，商为整数；
若 $ j $ 是合数且 $ j > 4 $，则 $ j \mid (j-1)! $，故 $ (j-1)! + 1 \equiv 1 \pmod{j} $，商非整数 → $ \cos^2 $ 值
特殊小合数 $ j=1,4 $ 需单独处理（$ j=1 $ 无定义，$ j=4 $：$ 3!+1 = 7 $，$ 7/4 = 1.75 $，$ \cos^2(\pi \cdot 1.75) = \cos^2(1.75\pi) = \sin^2(0.25\pi) = 0.5 $ → floor 为 0）。

因此，无需计算超大阶乘！只需判断 $ j $ 是否为素数（用试除法），即可直接得到 floor(cos²(...)) 的值：

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

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

    # 估算上界：第 n 个素数 < n*(log n + log log n) (n≥6)，保守取 2**n 不必要且低效
    # 改用动态扩展搜索范围
    candidate = 2
    count = 0
    while count < n:
        if is_prime(candidate):
            count += 1
            if count == n:
                return candidate
        candidate += 1
    return candidate

⚠️ 注意事项：

Willans 公式本质是“存在性证明”，非实用算法：时间复杂度为 $ O(2^n \cdot n!) $，比朴素试除慢数个数量级；
原始代码中 2**n 上界过于宽松（第 8 个素数是 19，却遍历到 256），应改用素数定理估算或动态增长；
pow(n / sum, 1/n) 在 sum=0 时会报错（如 i=1 时无素数），需加保护；
math.floor(pow(...)) 可简化为 int(...)，但逻辑不变。

? 总结：面对数学公式的编程实现，优先考虑符号化约简而非数值硬算。Willans 公式的价值在于理论趣味性，工程中请始终选用筛法（如埃氏筛、分段筛）或优化试除。若坚持公式验证，建议用 SymPy 进行符号计算，避免浮点陷阱。

# python # 编码 # app # ai # cos # overflow # 三角函数

相关栏目：【网站优化151355 】【网络推广146373 】【网络技术251813 】【 AI营销90571 】