CODEWITHSUNDEEP
python
user86925
user86925

Reputation: 123

Handling large integers in python

I had written a program in python to find b such that a prime number p divides b^2-8. The range for b is [1, (p+1)/2].

For small integers it works, say only up to 7 digits. But not for large integers, say for p = 140737471578113. I get the error message 

    for i in range (2,p1,1):
MemoryError

I wrote the program as 

#!/usr/bin/python3
p=long(raw_input('enter the prime number:'))
p1=long((p+1)/2)
for   i in range (2,p1,1):
    s = long((i*i)-8)
    if (s%p==0):
        print i

Upvotes: 2

Views: 681

Answers (1)

Martijn Pieters
Martijn Pieters

Reputation: 1121216

On Python 2, the range() function creates a full list of integers:

>>> range(3)
[0, 1, 2]

On a 64-bit machine just the 70368735789056 integers needed for that list would require almost 1.5 petabytes of memory, not even counting the list object with that many 64-bit pointers. It is no wonder you ran out of memory.

Normally, you'd use the xrange() function instead to produce a sparse range iterable, but that object cannot handle long numbers. A while loop would suffice here:

i = 2
while i < p1:
    s = long((i*i)-8)
    if (s%p==0):
        print i
    i += 1

Upvotes: 3

Related Questions