基于C.P. Willans公式的Python质数生成代码溢出问题求助

问题根源 #

你遇到的OverflowError是因为计算第8个质数时，循环中的j会达到255，此时factorial(254)是一个极其庞大的整数。将这个整数转换为浮点数时，超出了Python浮点数的表示范围，导致溢出错误。原代码中通过余弦函数计算的部分，本质上是利用威尔逊定理判断j是否为质数，完全可以用整数运算替代浮点数操作来避免这个问题。

核心原理：威尔逊定理 #

威尔逊定理指出：当且仅当j是质数时，(j-1)! ≡ -1 mod j（即(j-1)! % j == j-1）。基于这个定理，我们可以直接用整数模运算替代原代码中的余弦函数计算，彻底规避浮点数溢出。

修改后的代码 #

def nth_prime(n):
    if isinstance(n, int) and n > 0:
        end_sum = 0
        max_i = 2 ** n
        for i in range(1, max_i + 1):
            count = 0
            for j in range(1, i + 1):
                if j == 1:
                    # 对应原公式中j=1的情况，结果为1
                    count += 1
                else:
                    # 计算(j-1)! mod j，避免生成超大整数
                    wilson_mod = 1
                    for k in range(1, j):
                        wilson_mod = (wilson_mod * k) % j
                    # 威尔逊定理判断j是否为质数
                    if wilson_mod == j - 1:
                        count += 1
            # 简化原公式中的pow和floor操作，用逻辑判断替代
            end_sum += 1 if count <= n else 0
        return end_sum + 1
    else:
        raise ValueError("请输入正整数")

print(nth_prime(8))  # 输出19，即第8个质数

额外说明 #

• 该代码完全使用整数运算，彻底解决了浮点数溢出问题。
• 对于n=8，代码需要遍历到2^8=256，运行速度较慢（这是Willans公式本身的理论特性，并非代码优化问题）。若需要更高效的质数生成，可使用埃氏筛法等实用算法。

内容的提问来源于stack exchange，提问作者Jan Rojek