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.