python - 在 python 中处理大整数

Question

我用 python 编写了一个程序来查找 b，这样素数 p 可以整除 b^2-8。 b 的范围是 [1, (p+1)/2]。

对于小整数它有效，比如最多 7 位数字。但不适用于大整数，比如 p = 140737471578113。我收到错误消息

    for i in range (2,p1,1):
MemoryError

我把程序写成

#!/usr/bin/python3
p=long(raw_input('enter the prime number:'))
p1=long((p+1)/2)
for   i in range (2,p1,1):
    s = long((i*i)-8)
    if (s%p==0):
        print i

Answer 1

在 Python 2 上，range() 函数创建一个完整的整数列表:

>>> range(3)
[0, 1, 2]

在 64 位机器上，仅该列表所需的 70368735789056 个整数就需要将近 1.5 PB 的内存，甚至不包括具有那么多 64 位指针的列表对象。难怪你内存不足。

通常，您会使用 xrange() function而是生成一个稀疏范围的可迭代对象，但该对象无法处理长数字。 while 循环在这里就足够了:

i = 2
while i < p1:
    s = long((i*i)-8)
    if (s%p==0):
        print i
    i += 1