[Edu-sig] Numeracy + Computer Literacy: more upgrades
Kirby Urner
pdx4d@teleport.com
Fri, 18 Feb 2000 08:55:28 -0800
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