current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.
up vote 0 down vote favorite

I wrote a program to find prime factors of a number. When I give a large number(600851475143) as input, MemoryError pops up. Below is the code: 

def fact(a):
    factors = []
    for i in range(1,a+1):
        if a%i == 0:
            factors.append(i)
    return factors 

num = raw_input(">>  ")
#600851475143
a = b = []
a = fact(long(num))    
for i in range(0,len(a)):
    b = fact(a[i])
    if len(b) <= 2:
        print a[i]

From browsing I came to know that Python makes use of Computer memory - RAM. I am using Python in Unbuntu without changing its configuration. Should I change anythig to work on 64-bit machine. Or should I use any additional function(s) to get around this error

share|improve this question
4  
Your basic issue is that your algorithm is likely using too much memory. If you are using python 2, then range(1, a+1) is attempting to create a list with 600851475143 elements. This is probably not what you want as each element will be an integer and each integer takes 4 bytes. (Also, this question isn't appropriate for Programmers as you really need a code review and to understand in particular how python works.) –  Steven Burnap Jan 13 at 18:56
    
(You probably want xrange, which is a generator that returns elements to the for loop as needed. That may not be the only issue you are having, though.) –  Steven Burnap Jan 13 at 18:58
1  
Your list is 2.2TB big. Switching to a 64 bit machine will not help. You need to install more than 2TB of RAM (which to be fair will require a 64 bit OS to use). Or re-think your algorithm. –  Jörg W Mittag Jan 14 at 5:23
    
In addition to memory issues (just because no others have pointed out so far), there are some more efficient algorithms for calculating the list of factors of a number, or to decide whether a number is prime, or to generate a list of prime numbers. While most people talk about time complexity, there is also the related concept of space complexity. –  rwong Mar 14 at 20:48

1 Answer 1

up vote 0 down vote

There are various ways to measure the memory used by your program, and you may be able increase per-user limits or something.

However, you don't need to allocate that memory in the first place, since you can just generate the sequence without storing it all:

def fact(a):
    "just return a generator for the sequence you want"
    return (i for i in xrange(1,a+1) if a % i == 0)

Note that you can also iterate directly over sequences without needing to index them repeatedly:

for b in fact(long(num)):
    print b
share|improve this answer
1  
The list in the question is 2.2TB big, I doubt raising resource limits will help :-D –  Jörg W Mittag Jan 14 at 5:24
    
Well, maybe the OP can wait until 2035, when 8TB SIMMS are available. –  Steven Burnap Apr 13 at 22:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.