# Optimizing a program

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

625 Views
``````import pickle

# Loop to start over (Part 1/2)
done = False
while done == False:

userinput = int(input('Enter a number: '))
# You only have to look to the sqrroot
rootinput = int(userinput**0.5)
# Opens a list with all earlier found primenumbers
primelist = open('C:\Python31\PrimeListMaker\primelist.pkl', 'rb')
primelist.close()
i = plist[-1]
# Program that determines if a number is a prime
import isprime

# 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) == True:
plist.append(i)
print(rootinput - i)
i = i + 2

# Open the primelist file again and save the new plist
primelist = open('C:\Python31\PrimeListMaker\primelist.pkl', 'wb')
pickle.dump(plist, primelist)
primelist.close()

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)

# Loop to start over (Part 2/2)
yeah = input('Start over? Y/N: ')
if yeah == "N":
done = True``````
jcao219 18

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?

jcao219 18

Nothing built-in that I know of.

TrustyTony 888
jon.kiparsky 326

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.

TrustyTony 888

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.'``````
TrustyTony 888

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.'``````
TrustyTony 888

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')
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)``````
TrustyTony 888

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')
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:

# 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:
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`))``````
vegaseat 1,735

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.