python - 数值错误

Question

我写了一个快速筛子来测试一个数字是否是素数。我有两个问题:

1) 我测试了一个 200 位素数，它错误地表明它不是素数。我相信这归因于浮点错误(或类似的错误)。我怎样才能使这个更准确？

2)有更好的写法吗？我使用十进制来处理更大的数字。这是最好的方法吗？

import math
from decimal import *
def isprime(n):
    i = 2
    a = 1
    if n == 1:
        return 0
    if n == 2 or n == 3:
        return 1
    while i < n**0.5 + 1:
        if Decimal(math.fmod(n,i)) == 0:
            a = 0
            i = n
        if Decimal(math.fmod(n,i)) != 0:
            i += 1
            a = 1
    return a

Answer 1

标准double浮点格式只能表示精确到 2^53 的整数(9007199254740992，16 位数字)；从那时起，可表示的整数之间就存在差距，并且随着数字变大，这些差距也会变得更大。

Python 的 64 位版本本身使用 64 位整数，在其他平台上您可以使用 numpy的int64。这不会让你接近 200 位数字，但它会让你远离 32 位整数范围，让简单的代码变得非常慢。

例如，在处理最大 2^32 的整数或 sqrt(2^32)/2 = 32767 时，试除法只需要考虑最多 pi(sqrt(2^32)) = 6542 个潜在的小素因数奇数候选除数加上数字 2，或者当使用阶数高于 2 的轮时，介于这两个极端之间。在 2^64 附近，要测试的小素因数的数量为 pi(sqrt(2^64)) = 203,280,221 已经...

超过 2^32 的确定性素数测试是 Miller-Rabin 等算法的领域或Baillie-PSW 。当与某些精心选择的碱基组一起使用时，Miller-Rabin 在某些阈值(高达 2^64 左右)内具有确定性；请参阅The best known SPRP bases sets 。 Baillie-PSW 的确定性也至少高达 2^64。

这意味着超过 2^64 时，您需要使用某种大整数类型，并且必须使用概率算法进行素数测试(为您提供“工业级”素数，而不是经过验证的素数)。或者计划花费大量时间来实际证明 200 位数字的素数... 200 位数字有 100 位数字的平方根(大约 300 位)，因此即使计算所有潜在的小质因数插入天真的试炼测试不再可行。