2

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
user86925
  • 123
  • 5

1 Answers1

3

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
Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
  • $@Martijn Pieters$, Thank you for the help. I use python 2.7. I tried using while loop, answer comes but takes a long time. –  Oct 22 '13 at 11:14
  • $@Martijn Pieters$,once again for large $p=9444732965601851473921$ this does not work. Is there any way to make it work? – user86925 Oct 22 '13 at 11:31
  • 2
    Think about this for a little. You are planning to loop 4722366482800925736960 times to get an answer. Lets say you can execute that loop 1 million times per second, it would only take 150 million years to execute all iterations. Perhaps you need to find yourself a more efficient algorithm? – Martijn Pieters Oct 22 '13 at 11:35
  • What exactly do you mean by "xrange cannot deal with *long* numbers"? Answer: Python has a "long integer" datatype (for efficiency reasons). Usually you just use "plain integer" which is limited to a C long (in the C implementation). – Sarien Oct 22 '13 at 12:19
  • 2
    @Sarien: `xrange()` cannot handle int values beyond `sys.maxint`, at which point Python integers are transparently implemented as type `long`. – Martijn Pieters Oct 22 '13 at 12:22
  • the best way is to use Tonelli-shanks algorithm, again there is a problem of large integers http://codereview.stackexchange.com/questions/14982/tonelli-shanks-algorithm-in-python – user86925 Oct 23 '13 at 10:08
  • I already showed you you can replace a `xrange()`-based loop with a `while` loop. There are also [other ways to replace it](http://stackoverflow.com/questions/1482480/xrange2100-overflowerror-long-int-too-large-to-convert-to-int) posted here on Stack Overflow. – Martijn Pieters Oct 23 '13 at 10:17