Memory error in Python for loops

Question

I'm currently trying to find the largest prime number contained within another large number.

maxlen = 1024
for i in range(1023, -1, -1):
    maxlen -= 1
    number = ""
    for k in range(maxlen, -1, -1):
            number = pi[k] + number
            if isprime(number) == True:
                    print number

isprime() is a function that checks if the number is a prime (pretty standard). this works pretty well up to a certain point where I get a MemoryError.

This is not because the number checked by the function is too large since it happens around the 6th run of the first for loop.

I've already tried gc.enable() and gc.collect() without any positive result.

Does anyone have an idea how to fix this?

Edit: definition of pi and isprime() as per request:

f = open("/root/number", "r")
pi = f.read()
f.close()

where the file "number" contains the original number in which I'd like to find the prime.

def isprime(n):
    n = abs(int(n))
    if n < 2:
            return False
    if n == 2:
            return True
    if not n & 1:
            return False
    for x in range(3, int(n**0.5)+1, 2):
            if n % x == 0:
                    return False
    return True

Traceback:

Traceback (most recent call last):
  File "./primal.py", line 36, in <module>
    if isprime(number) == True:
  File "./primal.py", line 24, in isprime
    for x in range(3, int(n**0.5)+1, 2):
MemoryError

What is pi? And why aren't you just using for maxlen in range(1023, -1, -1):? — JAB
– JAB, Commented Jun 29, 2012 at 13:16
And copy us the error line, if I recall Python gives you some details to find out at which line the error occurred. By the way, you don't need the "== True" part of the if statement. — Bane Bojanić
– Bane Bojanić, Commented Jun 29, 2012 at 13:17
Building strings is also quite expensive and unnecessary in your case. Instead of number = "" and number = pi[k] + number, do the math with integers: number = 0 and number = (number * 10) + int(pi[k]). Then, you can also drop the int(n) within is_prime. — Ferdinand Beyer
– Ferdinand Beyer, Commented Jun 29, 2012 at 13:27

Martijn Pieters · Accepted Answer · 2012-06-29 13:26:49Z

8

Use xrange instead of range, most importantly in isprime, here:

for x in xrange(3, int(n**0.5)+1, 2):

xrange doesn't create the whole list in memory, while range does, but you are not using the results after you iterated over them.

Another tip: just test for isprime(n), there is no need to see if it is equal to True, that is what if does. :-)

if isprime(number):  # Only works if isprime(number) is boolean True
    ...

edited Jun 29, 2012 at 13:26

answered Jun 29, 2012 at 13:21

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

JAB Over a year ago

Generators and lazy evaluation in general sure are great for memory-intensive stuff.

fragman Over a year ago

great tips, thx. still doesn't work though but I'll keep searching for those errors myself first

Martijn Pieters Over a year ago

@fragman: remember to use a new SO Question for each new problem you encounter (and search for existing answers).

fragman Over a year ago

Thanks, I'll keep that in mind. Since I don't get the MemoryError anymore this seems to be the case. However the program still dies at the exact same point as before...

Martijn Pieters Over a year ago

@fragman: presumably with a different error now; which is a new problem. :-)

|

Levon · Accepted Answer · 2012-06-29 13:29:10Z

5

If this is in Python v 2.x use xrange() instead of range(). range() generates a list all at once in memory, while xrange() works "on-demand", generating a value each time you need one.

In Python 3.x xrange() is gone, and range() acts like xrange() used to.

To quote from What's New in Python 3:

range() now behaves like xrange() used to behave, except it works with values of arbitrary size. The latter no longer exists.

edited Jun 29, 2012 at 13:29

answered Jun 29, 2012 at 13:22

Levon

144k35 gold badges205 silver badges194 bronze badges

2 Comments

fragman Over a year ago

Thanks for this explanation. I'm still using 2.7, so I changed it to xrange(), but I'll keep that in mind when I switch to 3.x

Levon Over a year ago

@fragman You are welcome. I recently started to use v3 (in addition to continue to use 2.7) and found the "What's New .. in 3" an interesting/informative read.

Collectives™ on Stack Overflow

Memory error in Python for loops

2 Answers 2

6 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related