0

I am using the Sieve of Eratosthenes in a Python program to find prime factors. Here is the code -

import time
import sys

p=[]

def sieve(n):
    p.append(False)   # 0 isn't prime
    p.append(False)   # 1 isn't prime
    i=2
    while (i<=n):
        if i%2==0:
            p.append(False)
       else:
            p.append(True)
       i+=1
    #creating a sieve and putting even numbers as false and odd as true
    #Even numbers can never be prime except 2 which will now become true

    p[2]=True

    sq=int(n**0.5)  #storing square root of n
    i=3
    while (i<=sq):
        k=i*i
        while k<=n:
            p[k]=False
            k+=(2*i) 
        i+=2

def primefactors(n,x):
    print "The prime factors are : "
    if(n%2==0):
        print 2
        while(n%2==0):
            n/=2
    i=3
    while(i<len(p)):
        if(n==1):
            break 
        if(p[i]):
           if(n%i==0):
               print i
               while(n%i==0):
                    n/=i
        i+=2
    if n==x:
        print None
    elif n!=1:
        print n

def main ():
    print "Enter number to be factored "
    n=raw_input()
    n=int(n)
    start=time.clock()
    sieve(n**0.5+1)
    primefactors(n,n)
    end=time.clock()
    print "Seconds : "+str(end-start)

main()

Now, when I am trying factor 18 digit numbers I am receiving memory error while creating the list. However, Windows task manager shows only 1.48 GB RAM used, while I have around 2.2 GB usable RAM. What is the reason behind this?

I have added a screenshot of the task manager when the memory error occurred.(cannot post images yet here so here is the link - Image)

Also, I know that there are other methods for factoring primes faster, but I would just like to know why this memory error is happening before the RAM is totally utilised.

2 Answers 2

0

Check here

Therefore the maximum size of a python list on a 32 bit system is 536,870,912 elements.

0

python is reserving a continous space for your list. if your list has grown to the reserved space python allocates a bigger space and copies your elements to the new location. this resizing fails latest when your list has grown to half of the available memory.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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