[Edu-sig] Hello from a CS Teacher

Kirby Urner pdx4d@teleport.com
Fri, 11 Feb 2000 17:31:41 -0800

```At 07:07 PM 02/11/2000 -0600, Dustin James Mitchell wrote:
>On Fri, 11 Feb 2000, Kirby Urner wrote:
>
>>    while len(primes)<nbprimes:
>>        # 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 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

```