OverflowError Python int too large to convert to C long

Solution 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.