Piet van Oostrum wrote:
Dave Angel <da...@dejaviewphoto.com> (DA) wrote:

DA> It would probably save some time to not bother storing the zeroes in the
DA> list at all.  And it should help if you were to step through a list of
DA> primes, rather than trying every possible int.  Or at least constrain
DA> yourself to odd numbers (after the initial case of 2).

...
# Based upon http://code.activestate.com/recipes/117119/

D = {9: 6} # contains composite numbers
XXX Dlist = [2, 3] # list of already generated primes
  Elist = [(2, 4), (3, 9)] # list of primes and their squares

XXX def sieve():
XXX   '''generator that yields all prime numbers'''
XXX   global D
XXX   global Dlist
 def sieve2():
     '''generator that yields all primes and their squares'''
     # No need for global declarations, we alter, not replace
XXX   for p in Dlist:
XXX       yield p
XXX   q = Dlist[-1]+2

      for pair in Elist:
          yield pair
      q = pair[0] + 2

    while True:
        if q in D:
            p = D[q]
            x = q + p
            while x in D: x += p
            D[x] = p
        else:
XXX           Dlist.append(q)
XXX           yield q
XXX           D[q*q] = 2*q
              square = q * q
              pair = q, square
              Elist.append(pair)
              yield pair
              D[square] = 2 * q
        q += 2

def factorise(num):
    """Returns a list of prime factor powers. For example:
        factorise(6) will return
        [2, 2] (the powers are returned one higher than the actual value)
        as in, 2^1 * 3^1 = 6."""
    powers = []
    power = 0
XXX   for factor in sieve():
      for factor, limit in sieve2():
        power = 0
        while num % factor == 0:
            power += 1
            num /= factor
XXX       if power > 0:
          if power: # good enough here, and faster
            # if you really want the factors then append((factor, power))
            powers.append(power+1)
XXX       if num == 1:
XXX           break
XXX   return powers
          if num < limit:
              if num > 1:
                  # if you really want the factors then append((num, 1))
                  powers.append(2)
              return powers

OK, that's a straightforward speedup, _but_:
     factorize(6) == [2, 2] == factorize(10) ==  factorize(15)
So I am not sure exactly what you are calculating.


--Scott David Daniels
scott.dani...@acm.org
--
http://mail.python.org/mailman/listinfo/python-list

Reply via email to