[Edu-sig] Hello from a CS Teacher

[Kirby Urner]

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