OverflowError Python int too large to convert to 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

when I run this code it is throwing different types of errors for different inputs.

The following is the one kind of input

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

This is for second input

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

And this is for third output

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

Actually I was writing code for Fermat factorization to find the factors of a given number. And my requirement is even if give a hundred digit number as input it should give the output for that input number.

Is there any way to get rid this kind of problem? I am using Ubuntu with python 2.7.5+

Answer 1

Annoyingly, in Python 2, xrange requires its arguments to fit into a C long. There isn't quite a drop-in replacement in the standard library. However, you don't quite need a drop-in replacement. You just need to keep going until the loop breaks. That means you want itertools.count, which is like an xrange that just keeps going:

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

Also, note that your code has other bugs. It attempts to apply Fermat factorization to even numbers, but Fermat factorization doesn't work on even numbers. Additionally, it fails to consider the case where n is a square, so it won't work for n=9.