22
#!/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+

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
Suhas
  • 231
  • 1
  • 2
  • 3
  • 3
    Your first two tracebacks is for code that you didn't post; you were using `range()` instead of `xrange()`, producing lists with too many elements. You should not try and produce loops for such *huge* factors in any case. Your code would never complete in any reasonable amount of time *anyway*. – Martijn Pieters Mar 01 '14 at 12:04
  • Where in [Fermat's factorization algorithm](https://en.wikipedia.org/wiki/Fermat's_factorization_method) do you see the need to create such loops in the first place? – Martijn Pieters Mar 01 '14 at 12:10
  • You can't use Fermat factorization for even numbers. – user2357112 Mar 01 '14 at 12:14

2 Answers2

40

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.

user2357112
  • 260,549
  • 28
  • 431
  • 505
0

Btw if you still want a factor function that works with big numbers, here:

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)))

So now you only need to say:

>>> factors(largenumhere)

For a load of factors :D

WhyAreYouReadingThis
  • 342
  • 3
  • 16