OverflowError Python int太大而无法转换为C long

Question

#!/usr/bin/python
import sys,math
n = input("enter a number to find the factors   :   ")
j,flag,b= 0l,False,0l
for b in xrange(1,n+1):
    a = n + (b*b)
    j = long(math.sqrt(a))
    if a == j*j:
        flag = True
        break
if flag:
    c = j+b
    d = j-b
    print "the first factor is   :   ",c ,"  and the second factor is   :   ",d

当我运行此代码时,它会为不同的输入抛出不同类型的错误.

以下是一种输入

linux@terminal:~$ ./fermat.py
enter a number to find the factors   :   544564564545456
Traceback (most recent call last):
  File "./fermat.py", line 8, in <module>
    for b in range(1,n+1):
MemoryError

这是第二次输入

linux@terminal:~$ ./fermat.py
enter a number to find the factors   :   28888888888888888888888888888888888444444444444444444444444
Traceback (most recent call last):
  File "./fermat.py", line 8, in <module>
    for b in range(1,n+1):
OverflowError: range() result has too many items

这是第三次输出

linux@terminal:~$ ./fermat.py
enter a number to find the factors   :   28888888888888888888888888888888888444444444444444444444444
Traceback (most recent call last):
  File "./fermat.py", line 8, in <module>
    for b in xrange(1,n+1):
OverflowError: Python int too large to convert to C long

实际上我正在为Fermat分解编写代码以找到给定数字的因子.而且我的要求即使给出一个百位数作为输入它应该给出输入数字的输出.

有没有办法摆脱这种问题？我正在使用Ubuntu和python 2.7.5+

Answer 1

令人讨厌的是,在Python 2中,xrange要求其参数适合C long.标准库中没有完全替代品.但是,您不需要直接替换.你只需要继续循环直到循环break.这意味着你想要itertools.count,就像一个xrange只是继续前进:

import itertools
for b in itertools.count(1):
    ...

另请注意,您的代码还有其他错误.它试图将费马分解应用于偶数,但费马分解对偶数不起作用.此外,它没有考虑n广场的情况,所以它不适用n=9.