Simple Python Question about memory usage and for loops

Question

I am currently taking an intro to cryptography course that is using python as the language in the class.

The problem we have is quite simple, and all it is asking us to do is figure out the smallest prime divisor for some integer n passed into the function, and will return said prime number.

The IDE we are using is telling me that the program keeps getting interrupted because I am running out of memory.

Below is my code:

    def smallest_prime_divisor(n):
        if(n%2==0):
            return 2;
        for i in range(3, n):
            if(n%i==0):
                if(is_prime(i)):
                    return i;
    return n;

    for n in range(1,120):
        x=2^n;
        x+=1;
        smallest_prime_divisor(x)

I don't believe the issue lies in the smallest_prime_divisor function, but somewhere in my second for loop, as I have tested quite a few numbers using just

    smallest_prime_divisor(x); #where x is equal to all integers 1-20

I know this seems like a simple question but it is driving me mad that I can't seem to find the right words to search google for the correct answer.

note, `x=2^n` is *not* doing exponentiation in python (`^` is bitwise XOR). python syntax for power is `**`. So `2**n` for example. I'm not really sure what you're doing with `x` though, your description of the task at hand doesn't match up. — Paritosh Singh, Jan 30 '20 at 21:18
this runs fine on my machine. how have you implemented your is_prime function? — swaggy p, Jan 30 '20 at 21:22
@swaggyp He is likely doing it with recursion for him to be getting a memory error. — felipe, Jan 30 '20 at 21:22
The way your loop is setup **you don't need the `is_prime(...)` method at all**. The first divisor of `n` you encounter in the sequence 2, 3, ... n\**(0.5) is guaranteed to be prime. See if you can convince yourself of that. This allows you to simplify your `smallest_prime_divisor()` method. — President James K. Polk, Jan 30 '20 at 22:36

score 2 · Answer 1 · answered Jan 30 '20 at 21:24

Your issue is likely with your is_prime() function that if I had to guess, is recursively calling itself. Here is an implementation of is_prime using Wilsom's theorem that will run without returning a memory error.

from math import factorial

def is_prime(n):
    return factorial(n - 1)  % n == n - 1

def smallest_prime_divisor(n):
    if(n%2==0):
        return 2
    for i in range(3, n):
        if(n%i==0):
            if(is_prime(i)):
                return i
    return n

for n in range(1,120):
    # Notice this line as well 'Paritosh Singh' mentioned in the comments why it is ** and not ^.
    x=2**n
    x+=1
    smallest_prime_divisor(x)

Notice the change between x=2^n and x=2**n as well.

In other news, recursive calls are stupid as they make you run out of stack space. — Maarten Bodewes, Jan 30 '20 at 23:52

score 0 · Answer 2 · answered Jan 31 '20 at 03:47

You're using Python2, aren't you?

The problem is in this line of the smallest_prime_divisor() function:

    for i in range(3, n):

In Python2, range(x,y) generates a list of every number from x to y-1. If y-x is up in the billions, you're going to be eating up a lot of memory.

The solution is simple; replace range with xrange, which only generates the next number in the list when you ask for it.

Simple Python Question about memory usage and for loops

2 Answers2