How to avoid MemoryError

Question

I'm trying to find a number's max prime factor. Here is my code, but I don't know are my codes working correctly or not because I'm getting MemoryError all the time;

lst = []
for x in range(3,round(600851475143**0.5)+1):
    for y in range(2,x+1):
        if x%y==0:
            for z in range(2,x+1):
                if x%z!=0:
                    lst.append(x)
print (max(lst))

Here is the traceback;

>>> 
Traceback (most recent call last):
  File "C:--------", line 19, in <module>
    lst.append(x)
MemoryError
>>>

After 20-30 seconds process, I got this error.How to avoid this one?

Edit: Actually, I guess that it may be MemoryError so as you see I put in the first range function, square root of that number 600851475143**0.5. Then I use round to aviod from float. But I still got MemoryError.

`I'm trying to find a number's max prime factor` as I said in my question. So this is the number as you see in the question `600851475143` — Darer., Jan 28 '15 at 16:53
These are 3 nested for loops man , Its memory consumption is approx. O(n^3) , you need more than a desktop computer for that I guess — ZdaR, Jan 28 '15 at 16:54
i7 3.8GHZ 8-processor isn't good? 16gb ram also. Computer is really powerfull I don't think it's about computer — Darer., Jan 28 '15 at 16:54

score 1 · Answer 1 · answered Jan 28 '15 at 16:57

1

if x%y==0:
    for z in range(2,x+1):
        if x%z!=0:
            lst.append(x)

I'm guessing what you're trying to do here is, append x to lst if x is prime. But what you're actually doing is, appending x to lst for every number less than x that isn't a factor of x. Ex. 6 will be appended twice because both 4 and 5 are not a factor of 6.

If you want to append x only when all z's are not a factor of x, then try:

if x%y==0:
    if all(x%z != 0 for z in range(2, x)):
        lst.append(x)

answered Jan 28 '15 at 16:57

Kevin

74,910
12
133
166

Yes I'm checking if `x` is prime on there, isn't that correct? – Darer. Jan 28 '15 at 16:58
I'm still waiting the result with your codes btw, I have a strong computer but process is slow. Wondering why – Darer. Jan 28 '15 at 17:07

score 0 · Answer 2 · edited Jun 20 '20 at 09:12

From the python documentation:

exception MemoryError

Raised when an operation runs out of memory but the situation may still be rescued (by deleting some objects). The associated value is a string indicating what kind of (internal) operation ran out of memory. Note that because of the underlying memory management architecture (C’s malloc() function), the interpreter may not always be able to completely recover from this situation; it nevertheless raises an exception so that a stack traceback can be printed, in case a run-away program was the cause.

You're putting too many elements into lst.

There are more efficient prime factorization algorithms than the one you wrote, which can be looked up on wikipedia.

Here's one from SO, running in O(sqrt(n)) time: http://stackoverflow.com/a/412942/4168787 — SmeltQuake, Jan 28 '15 at 16:59

How to avoid MemoryError

2 Answers2