[Tutor] recursive factoring

[Kirby Urner]

Here's another approach which doesn't keep scanning
the same numbers over and over for primes.  Instead,
a sieve is run against n right off the bat, and then
isprime just uses this as a lookup list:

  class Primes:
	def __init__(self,n):
	    self.primes = sieve(n)
	def __call__(self,val):
	    if val in self.primes:
		return 1
            else:
	        return 0
	
  def factor(n):
	isprime = Primes(n)
	def getnext(n):
	   if isprime(n):
	      return [n]
           for i in range(2, math.sqrt(n)+1):
	      if isprime(i) and n%i==0:
		  return [i] + getnext(n/i)
	return getnext(n)

But of course this means you need a sieve function
as well.  Here's one:

def sieve(n):
    """
    In-place sieving of odd numbers, adapted from code
    by Mike Fletcher
    """
    candidates = range(3, n+1, 2)  # start with odds
    for p in candidates:
        if p:                   # skip zeros
	   if p*p>n: break     # done
	   for q in xrange(p*p, n+1, 2*p):  # sieving
		candidates[(q-3)/2] = 0
    return [2] + filter(None, candidates)  # [2] + remaining nonzeros

Kirby