At 07:07 PM 02/11/2000 -0600, Dustin James Mitchell wrote:

On Fri, 11 Feb 2000, Kirby Urner wrote:

...

while len(primes)<nbprimes: if addprime(i): primes.append(i) # skip even numbers (only 2 is prime) if i==2: i=i+1 else: i=i+1

Shouldn't the latter be i=i+2, to go to the next odd number?

Dustin -- Yes, exactly, good eye! The algorithm still worked, but less efficiently. Below is a variant which computes all prime numbers _up to a maximum_ i.e. get2max(). With this one in place, I'm able to do getfactors(), which lists all the prime factors of a number. I also threw in isprime(), which answers whether any number is a prime number (1 means yes, 0 means no). Action:

...

...

seive.getfactors(10981) [79, 139] seive.isprime(99901) 1 seive.getfactors(30012) [2, 2, 3, 41, 61] 2*2*3*41*61 30012

I'm not claiming this is the most efficient or super-elegant implementation of getfactor(). If others have pointers as to how to improve these examples (to put Python in a good light), I'm happy to hear them. But I'm not looking for a lot of error checking on the passed parameters. Yes you can crash these algorithms if you pass out-of-context values, but no, I'm not interested in cluttering up the code based on the "naive user from hell" model. Kirby primes = [2] # dynamic list of primes def get2max(maxnb): # return list of primes # maxnb = number not to exceed on list global primes # keep at module level while primes[-1]>maxnb: primes = primes[:-1] i=primes[-1] while i<=maxnb: if addprime(i): primes.append(i) if i==2: i=i+1 else: i=i+2 return primes def isprime(n): global primes # keep at module level retval = 0 primes = get2max(n) if n in primes: retval = 1 return retval def getfactors(n): global primes # keep at module level # return list containing prime factors of a number primefactors = [] primes = get2max(n) while not (n in primes): for i in primes: if n%i == 0: # no remainder primefactors.append(i) n = n/i break primefactors.append(n) return primefactors