数字E

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位）的整数；从这一点开始，可表示的整数之间存在间隙，并且这些间隙随着数字的增大而增大。在

64位版本的python本机使用64位整数，在其他平台上，您可以使用numpy的int64。这并不能让你接近200位数，但它让你远离32位的整数范围，让天真的代码变得非常缓慢。在

例如，当使用小于等于2^32的整数时，试算除法只需要考虑pi（sqrt（2^32））=6542个潜在的小素数，或者sqrt（2^32）/2=32767个奇数候选除数加上数字2，或者在使用阶数大于2的轮子时考虑这两个极端之间的某个地方。在2^64附近，要测试的小素数已经是pi（sqrt（2^64））=203280221。。。在

大于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位），所以即使计算所有可能的小素数来推动一个简单的试算测试，也不再可行。在