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.

tech96
  • 47
  • 1
  • 6

2 Answers2

0

Check here

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

Community
  • 1
  • 1
Laszlowaty
  • 1,295
  • 2
  • 11
  • 19
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.

stefan
  • 3,681
  • 15
  • 25