[Edu-sig] Numeracy + Computer Literacy: more upgrades

[Kirby Urner]

I realized my 3rd section on even/odd, prime/composite
numbers was using way more inefficient Python than 
necessary.

My isprime(n) function was invoking get2max(n), which 
lists all primes up to and including n.  Not required,
as we already see in sieve(n) -- just check prime divisors 
up to the 2nd root of n, and you'll know if you're dealing
with a prime.  And you don't even have to go that far
-- we're done the moment any prime so far divides evenly 
(the primes list is at the module level, and so persists 
between function calls).

So isprime(n) takes advantage of this, and computes _only_ 
the minimal number of new primes necessary, if any, to 
reach a verdict on n's primehood.

We're talking _serious_ improvement in speed here.  Used
to be that pascalpack(26) was about all I had patience 
for (checks Pascal's Triangle for primes to row 26). 
I'd go for coffee.  Now even pascalpack(64) runs very 
quickly (seconds).  Sheesh.  (Pascal's Triangle actually
contains precious few primes, and these are relatively 
low numbers in the next to first/last columns, so pushing
get2max to find all primes up to those _huge_ interior
numbers -- which all fail quickly in the new isprime() 
-- was maddness, just _maddness_ :-D).[1]

Also fun: I was able to come up with a recursive function 
for finding the prime factors of a number:

def getfactors(n):
   # return list containing prime factors of a number
   if isprime(n) or n==1: return [n]
   else: 
       for i in primes:
           if n%i == 0: # no remainder
               n = n/i
               return [i] + getfactors(n)

Usage:

>>> primes.getfactors(28)
[2, 2, 7]
>>> primes.getfactors(400562313)
[3, 17, 19, 479, 863]
>>> 3*17*19*479*863
400562313

Short and sweet!

Probably old hat for you Schemers out there, who do just about 
everything imaginable using recursion.  But for me, this was 
a breakthrough.

So, yes, I've had to modify 

  http://www.inetarena.com/~pdx4d/ocn/numeracy2.html 

to reflect these improvements, and upload the improved 
source code.

Kirby

[1] what I'd like to do next is upgrade that page to 
take into account more of what Jim Nugent is studying:
Pascal's Triangle with +1 or -1 added to the terms --
which gives you lots of primes (except he's using 
Pascal's Tetrahedron):

http://www.twne.com/jnugent/math/Article2.htm