Python - memory efficiency - range

Question

I am seeking ways to make the below minimal code for MaxPower() function more memory efficient & examples using my code.

Purpose of MaxPower(): for integers i and N_remainder, to return the maximum value of m such that i^m divides N_remainder.

MaxPower() is only called in the factorise() function if i divides N_remainder

Currently the linked code below has the following results for the number to factorise (wrote in standard form):

1. 1x10^8 - works fine. Two arrays of results produced and are correct
2. 5x10^8 - hangs Linux & OS is totally unresponsive. Computer needs hard restart.
3. 1x10^9 - gives memory error in terminal.

Python version used is 2.74 on Linux Mint 17.

I am currently learning python.

def MaxPower(i,N_remainder):
    m=1
    MxP=1
    for n in range (2, N_remainder + 1):        
        b = i**n    
        a = N_remainder % b
        if a==0:    
            m = m+1                 
        else: 
            MxP = m     
            break
    return MxP

Revised code since originally posted:

def MaxPower(i,N_remainder):
    m=1
    MxP=1
    for n in xrange (2, N_remainder + 1):       
        b = pow(i,n)        
        a = N_remainder % b
        if a==0:    
            m = m+1                 
        else: 
            MxP = m     
            break
    return MxP

I am aware of the following (which I haven't tried since new & out of my depth currently);

1. Could do more work in compiled C code - converting to "list comprehension"
2. Use threading & make sure each thread is deleted after use.

Answer 1

The Python 2 range function creates a list with one entry for each number in the given range. This entire list needs to be stored in memory, so for large values of N_remainder it can get pretty big.

Instead, there is the xrange function, which does almost the same thing. This uses constant memory, only storing the parameters and calculating each value only when it’s needed and not storing old values once they’re used. If you replace the call to range with a call to xrange, your function should use almost-constant memory.

Note that if N_remainder + 1 is too big for a python int, the xrange function won’t work, but the documentation provides an alternative.

---

Not a memory issue, but you don’t need the explicit calls to long; Python 2 automatically converts to the long type when necessary.