检查超大质数时Python出现"long int too large to convert to float"错误求助

我最近在尝试复刻Stack Overflow上那个经典的is_prime质数判断函数，结果碰到了两个大坑：

• 一开始用xrange处理超大数的时候，直接抛出了OverflowError: Python int too large to convert to C long，于是我自己写了个mrange函数绕开这个问题；
• 结果刚解决第一个问题，又碰到了long int too large to convert to float的错误，查了半天发现是math.sqrt在处理超大整数时的锅。

先贴一下我当时的问题代码片段：

# benchmarked on an old single-core system with 2GB RAM.
from math import sqrt
def is_prime(num):
    if num == 2:
        return True
    if (num < 2) or (num % 2 == 0):
        return False
    # 这里原本用xrange，后来换成了自定义的mrange，但还是报错
    for i in mrange(3, int(sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

问题根源 #

这个新错误是因为math.sqrt会把输入的超大整数转换成float类型，但float的精度是有限的，当整数大到一定程度时，就会超出float能表示的范围，直接触发类型转换错误。

解决方案：避免浮点转换，用整数比较替代 #

其实根本不需要用sqrt，我们可以直接在循环里用i*i <= num来判断是否需要继续循环，这样全程都是整数运算，完全不会碰到类型转换的问题。

修改后的完整函数（包含自定义mrange的优化版）：

def mrange(start, stop, step):
    current = start
    while current < stop:
        yield current
        current += step

def is_prime(num):
    if num == 2:
        return True
    if num < 2 or num % 2 == 0:
        return False
    # 用i*i <= num替代sqrt，全程整数运算
    for i in mrange(3, num, 2):
        if i * i > num:
            break
        if num % i == 0:
            return False
    return True

关键改动说明 #

• 去掉了math.sqrt的依赖，改用i*i <= num作为循环终止条件，彻底避免浮点转换；
• 循环里先判断i*i > num，如果成立就直接break，不用遍历到num，效率和原来用sqrt的版本一致；
• 自定义的mrange保持不变，继续解决xrange（Python2）/range（Python3在某些场景）的超大数问题。

这样修改后，不管是多大的质数，都能正常判断，不会再出现类型转换的错误啦。

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