OverflowError Python 整数过大无法转换为 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

其实我是在写一个用于费马分解的代码，目的是找出一个给定数字的因子。我的要求是，即使输入一个一百位的数字，它也应该能给出这个数字的输出。

有没有办法解决这种问题？我使用的是Ubuntu系统，Python版本是2.7.5以上。

Answer 1

顺便说一下，如果你还想要一个可以处理大数字的因子函数，这里有一个：

from math import sqrt
def factors(n):
return set(reduce(list.__add__,
            ([i, n//i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0)))

现在你只需要这样说：

>>> factors(largenumhere)

为了得到一堆因子 :D

Answer 2

在Python 2中，xrange这个函数有点麻烦，它要求你传入的参数必须适合C语言中的长整型。这意味着你不能随便传入很大的数字。而在标准库里没有完全可以替代的函数。不过，其实你不需要一个完全替代的函数。你只需要让循环一直进行，直到遇到break为止。这样的话，你可以使用itertools.count，这个函数就像是一个不停增长的xrange。

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

另外，你的代码还有其他问题。它试图对偶数使用费马分解法，但费马分解法对偶数是无效的。而且，它没有考虑到n是完全平方数的情况，比如n=9时，它也会出错。