Optimizing a program

One thing I see is while done==False You should change that to while not done Also, you should have the imports at the beginning, not in the middle of a while loop, since you only import once, usually at the beginning of execution.

Thanks.
Do you know if there's any built-in functions in Python that do the same as my code?

Nothing built-in that I know of.

See my reply to the old thread:
http://www.daniweb.com/forums/post1254961.html#post1254961

I'm new at this, but I have to wonder if it's more efficient to address your list of primes by subscripts or with something like
for x in plist:

but that's a question that would be answered by someone closer to the machine than I am (I've only been looking at python for a few days)

Also, I'm not sure if your assignment of z = x serves any purpose. Could you not just use x throughout the loop?

That's pretty minor, but small things in loops can get big, so dike it out if you don't need it.

Also check http://infohost.nmt.edu/tcc/help/lang/python/prime.html for prime test. You can picle the Prime object you create if you use the code, it is memorizing object. not Prime.factor(n) if n>1 else False == isprime(n)

# prime.py: Prime number object for Python
#--
# Written by John W. Shipman (john@nmt.edu), New Mexico Tech
# Computer Center, Socorro, NM 87801
#--
# $Revision: 1.7 $
# $Date: 1997/06/05 23:59:04 $
#--

from math import *

class Prime:
    """ Object for testing long integers for primality.
        Tests a number n by dividing it by all primes <= sqrt(n).
        Memoizes primes already found so that repeated use
        does not pay the performance penalty.

        Exports:
            .factor ( n )
                [ if n is a positive long integer ->
                    if n is prime ->
                      return None
                    else ->
                      return the smallest prime factor of n
                ]

            .factorize ( n )
                [ if n is a positive long integer ->
                    return a list of the prime factors of n
                ]

        State/invariants:
            ._p == A list of known primes
                INVARIANT: Excludes 1, and includes at least 2 and 3;
                all members are prime and sorted in ascending order.
            ._pMax == Upper limit of self._p
                INVARIANT: self._p is guaranteed to contain all
                primes <= self._pMax.

        Verified, June 1997, by Al Stavely.
    """


# - - -   _ _ i n i t _ _   - - -

    def __init__ ( self ):
        self._p     =  [ 2L, 3L, 5L ]
        self._pMax  =  6L


# - - -   f a c t o r   - - -

    def factor ( self, n ):
        """ [ if n is a positive long integer ->
                if n is prime ->
                  return None
                else ->
                  return the smallest prime factor of n
                in any case ->
                  self._p     :=  self._p with all necessary primes
                                  appended so that it contains all primes
                                  in the range [2,floor(sqrt(n))]
                  self._pMax  :=  max ( self._pMax, floor(sqrt(n)) )
            ]
        """

        #-- 1 --
        if  n < 4L:
            return None

        #-- 2 --
        #-[ limit  :=  the largest integer <= floor(sqrt(n))
        #-]
        limit  =  long ( sqrt ( float ( n ) ) )

        #-- 3 --
        #-[ self._p     :=  self._p with all necessary values
        #                   added so that it contains all primes <= limit
        #-] self._pMax  :=  max ( self._pMax, limit )
        #-]
        self._fill ( limit )

        #-- 4 --
        #-[ if there is an element E of self._p such that
        #   (E<=limit) and (E divides n) ->
        #     return the smallest such element
        #   else -> I
        #-]
        for f in self._p:
            #-- 4 body --
            #-[ if f > limit ->
            #     break
            #   else if f divides n ->
            #     return f
            #   else -> I
            #-]
            if  ( n % f ) == 0L:
                return f
            elif  f >= limit:
                break

        #-- 5 --
        return None


# - - -   . _ f i l l   - - -

    def _fill ( self, limit ):
        """ [ if limit is a positive long integer ->
                if self._pMax >= limit -> I
                else ->
                  self._p     :=  self._p with all primes P added
                                  such that (P <= limit)
                  self._pMax  :=  limit
        """

        #-- 1 --
        if  self._pMax >= limit:
            return

        #-- 2 --
        #--
        # Note: since the invariant guarantees that self._p
        # contains at least 3, and since all primes greater than
        # 3 are odd, our candidates are the odd numbers starting
        # at 2 + the last element of self._p.  We can't use a
        # `for' loop here because xrange() doesn't handle longs.
        #--
        i  =  self._p[-1] + 2L

        #-- 3 --
        #-[ self._p  :=  self._p with all primes P added
        #                such that (i <= P <= limit)
        #   i        :=  <anything>
        #-]
        while i <= limit:
            #-- 3 loop --
            #-[ if i is prime ->
            #     self._p  :=  self._p with i appended
            #   else -> I
            #   In any case ->
            #     i = i + 2L
            #-]
            if  not self.factor ( i ):
                self._p.append ( long(i) )

            i = i + 2L

        #-- 4 --
        self._pMax  =  limit


# - - -   . f a c t o r i z e   - - -

    def factorize ( self, n ):
        """ [ if n is a positive long integer ->
                return a list of the prime factors of n, excluding 1,
                and including n iff n is prime
            ]
        """
        #-- 1 --
        #-[ if n is prime ->
        #     f0  :=  None
        #   else ->
        #     f0  :=  the smallest prime factor in n
        #-]
        n   =  long(n)      # Permit calling with normal integers
        f0  =  self.factor ( n )

        #-- 2 --
        #-[ if f0 is None ->
        #     return [n]
        #   else ->
        #     result   :=  [f0]
        #     residue  :=  n / f0
        #-]
        if  not f0:
            return [n]
        else:
            result   =  [f0]
            residue  =  n / f0

        #-- 3 --
        #-[ result   :=  result with all prime factors of residue
        #                appended (except 1)
        #   residue  :=  <anything>
        #-]
        while  residue > 1:
            #-- 3 loop --
            #-[ if residue has a prime factor ->
            #     result  :=  result with the smallest prime factor of
            #                 residue appended
            #     residue :=  residue / (that smallest prime factor)
            #-]

            #-- 3.1 --
            #-[ if residue has a prime factor ->
            #     f0  :=  that factor
            #   else ->
            #     f0  :=  None
            #-]
            f0  =  self.factor ( residue )
            
            #-- 3.2 --
            #-[ if f0 is None ->
            #     result   :=  result with residue appended
            #     residue  :=  1
            #   else ->
            #     result   :=  result with f0 appended
            #     residue  :=  residue / f0
            #-]
            if  not f0:
                result.append ( residue )
                residue  =  1
            else:
                result.append ( f0 )
                residue = residue / f0

        #-- 4 --
        return result
prime=Prime()
for i in range(1000):
    if not prime.factor(i) if i>1 else False: print i, 'is prime.'

Better approach as prime finding is the sieve, if you need many of them:

import sys
sys.path.append('.')

from time import clock
from prime import Prime ## object from code of previous post
from math import sqrt,ceil

def sieveOfAtkin(end):
    """sieveOfAtkin(end): return a list of all the prime numbers <end
    using the Sieve of Atkin."""
    # Code by Steve Krenzel, <Sgk284@gmail.com>, improved
    # Code: http://krenzel.info/?p=83
    # Info: http://en.wikipedia.org/wiki/Sieve_of_Atkin
    assert end > 0, "end must be >0"
    lng = ((end // 2) - 1 + end % 2)
    sieve = [False] * (lng + 1)

    x_max, x2, xd = int(sqrt((end-1)/4.0)), 0, 4
    for xd in xrange(4, 8*x_max + 2, 8):
        x2 += xd
        y_max = int(sqrt(end-x2))
        n, n_diff = x2 + y_max*y_max, (y_max << 1) - 1
        if not (n & 1):
            n -= n_diff
            n_diff -= 2
        for d in xrange((n_diff - 1) << 1, -1, -8):
            m = n % 12
            if m == 1 or m == 5:
                m = n >> 1
                sieve[m] = not sieve[m]
            n -= d

    x_max, x2, xd = int(sqrt((end-1) / 3.0)), 0, 3
    for xd in xrange(3, 6 * x_max + 2, 6):
        x2 += xd
        y_max = int(sqrt(end-x2))
        n, n_diff = x2 + y_max*y_max, (y_max << 1) - 1
        if not(n & 1):
            n -= n_diff
            n_diff -= 2
        for d in xrange((n_diff - 1) << 1, -1, -8):
            if n % 12 == 7:
                m = n >> 1
                sieve[m] = not sieve[m]
            n -= d

    x_max, y_min, x2, xd = int((2 + sqrt(4-8*(1-end)))/4), -1, 0, 3
    for x in xrange(1, x_max + 1):
        x2 += xd
        xd += 6
        if x2 >= end: y_min = (((int(ceil(sqrt(x2 - end))) - 1) << 1) - 2) << 1
        n, n_diff = ((x*x + x) << 1) - 1, (((x-1) << 1) - 2) << 1
        for d in xrange(n_diff, y_min, -8):
            if n % 12 == 11:
                m = n >> 1
                sieve[m] = not sieve[m]
            n += d

    primes = [2, 3]
    if end <= 3:
        return primes[:max(0,end-2)]

    for n in xrange(5 >> 1, (int(sqrt(end))+1) >> 1):
        if sieve[n]:
            primes.append((n << 1) + 1)
            aux = (n << 1) + 1
            aux *= aux
            for k in xrange(aux, end, 2 * aux):
                sieve[k >> 1] = False

    s  = int(sqrt(end)) + 1
    if s  % 2 == 0:
        s += 1
    primes.extend([i for i in xrange(s, end, 2) if sieve[i >> 1]])

    return primes

n=1000000

t=clock()
print 'Number of primes found by sieve of Atkin',len(sieveOfAtkin(n))
t=clock()-t
print 'Calculation took:',t,'ms.'

print 'This should be same as this:'
prime=Prime()

print 'Primes upto',n,'by Prime object.'
t=clock()
prime.factor(n*n)
t=clock()-t

print '\n\nFound',len(prime._p),'primes. In',t*1000,'ms.'

I did some small fixes, like made the code to run with 2.6, logic about finishing the run... and made the code to run without saved file. Also it loads once the file and saves it once in the end.

from __future__ import print_function
import os,sys,pickle
# Program that determines if a number is a prime
import isprime
from prime_test import sieveOfAtkin as sieve

if sys.version.startswith('2.'):
    input=raw_input

# Loop to start over (Part 1/2)
primelist_file='primelist.pkl'
if os.path.exists(primelist_file):
    primelist = open(primelist_file, 'rb')
    plist = pickle.load(primelist)
    primelist.close()
else:
    print('No existing file, generating...')
    plist=sieve(1000000)

while True:

    userinput = input('Enter a number (empty to quit): ')
    if not userinput:
        # Open the primelist file again and save the new plist
        primelist = open(primelist_file, 'wb')
        pickle.dump(plist, primelist)
        primelist.close()
        break
    try:
        userinput = int(userinput)
        if userinput<1:
            raise ValueError
    except ValueError:
        print('Wrong number')
        continue

    # You only have to look to the sqrroot
    rootinput = int(userinput**0.5)
    # Opens a list with all earlier found primenumbers

    i = plist[-1]

    # Checks if sqrroot of userinput is bigger than the last element in plist (list with all stored primenumbers)
    if rootinput > i:
        i = i + 2
        # If rootinput > i and if a number between rootinput is a prime, append this prime to plist
        while rootinput > i:
            if isprime.isprime(i):
                plist.append(i)
                print(rootinput - i)
            i = i + 2

    x = 0
    factor = []
    # while x is smaller than plist elements - check if element is a factor in userinput
    while x < len(plist):
        if userinput % plist[x] == 0:
            z = x
            # if plist[x] is factor in userinput check how many times and write result to factor
            while userinput % plist[z] == 0:
                userinput = userinput/plist[z]
                factor.append(plist[z])
        x = x + 1
    # If userinput is not zero then userinput must now be a factor
    if int(userinput) != 1:
        factor.append(int(userinput))

    # Print all userinputs factors
    print(factor)

Here is version of program that just generates bigger sieves if necessary:

from __future__ import print_function
import os,sys,pickle
# Program that determines if a number is a prime
from isprime import isprime
from prime_test import sieveOfAtkin as sieve

if sys.version.startswith('2.'):
    input=raw_input

sievesize=100
primelist_file='primelist.pkl'

# Loop to start over (Part 1/2)
if os.path.exists(primelist_file):
    primelist = open(primelist_file, 'rb')
    plist = pickle.load(primelist)
    primelist.close()
    update=False
else:
    print('No existing file, generating...')
    plist=sieve(sievesize)
    update=True

while True:
    print('Highest prime available:',plist[-1])

    value = input('Enter a number (empty to quit): ')
    if not value:
        if update:
            print('Updating prime data')
            print('Last memorized prime:',plist[-1])
            # Open the primelist file again and save the new plist
            primelist = open(primelist_file, 'wb')
            pickle.dump(plist, primelist)
            primelist.close()
        break
    try:
        userinput = value = int(value)
        if value<1:
            raise ValueError
    except ValueError:
        print('Wrong number')
        continue

    # Opens a list with all earlier found primenumbers

    factor = []

    # while x is smaller than plist elements - check if element is a factor in value
    for x in plist:
        if value==1:
            print('1')
            break
        # if plist[x] is factor in value check how many times and write result to factor
        while not value % x:
            value = value//x
            factor.append(x)

        if value==1:
            break ## factoring ready

 
    # You only have to look upto the square root
    if value>1:
        if value<plist[-1]**2: ## possible factors checked allready
            factor.append(value)
            value=1
        elif isprime(value):
           factor.append(value)           
        else:       
            # Extend primes until value
            print()
            plistpos=len(plist) ## first new prime indes
  
            print('Generating longer sieve until',int(value**0.5),'...')
            plist=sieve(int(value**0.5))
            update=True
            print('Checking new primes...')
            
            for x in plist[plistpos:]:
                while not value % x:
                    value = value // x
                    factor.append(x)
                    
                if value==1:
                    break ## factoring ready
            else:
                factor.append(value)
            
    print('-'*20,'FACTORING','-'*20)
                
    # Print all values factors
    print(' * '.join([str(f) for f in factor]).center(52))
    print('-'*51)

##    check = reduce(lambda x,y:x*y, factor)
##    assert check==userinput,' '.join(('\nFactorization check failed:',`check`,'!=',`userinput`))

I am new to python and this is my first program. The program factorize a number given by a user. It also makes a list of all the primenumbers, that it finds and stores them in a file. Is there anybody who can see a way that I can make this program faster. Remember it is important that I still have a list with primenumbers.

All help is apriciated

Well, if you simply want to go for speed, then an interpreted language like Python is a poor choice.