I’ve been doing a few programming problems from Project Euler and having a ton of fun. Here are a few functions that I found useful and I’m sure someone else would as well.

### Prime Iteration

If you want to go through a list of integers and also know their prime factors, you could create some functions (the names should tell you what they do):

def primeFactor(n, primeSet = None) : ret = [] if primeSet == None : primeSet = primesToN(int(n ** 0.5)) for p in primeSet : while n % p == 0 : ret.append(p) n /= p if n != 1: ret.append(n) return ret def primesToN(n): if n==2 : return [2] elif n < 2 : return [] s = range(3, n+1, 2) mroot = n ** 0.5 half = (n+1) / 2 - 1 i = 0 m = 3 while m <= mroot: if s[i]: j = (m * m - 3) / 2 s[j] = 0 while j < half: s[j] = 0 j+ = m i = i + 1 m = 2*i + 3 return [2] + [x for x in s if x] def primes() : yield 2 D = {} q = 3 while True: p = D.pop(q, 0) if p: x = q + p while x in D: x += p D[x] = p else: yield q D[q*q] = 2*q q += 2

And then you could just do this:

primeRange = itertools.imap(lambda x : (tuple(util.primeFactor(x)), x), xrange(2, 1000)) for factors, number in primeRange : # do something with the factors and number

Now, this gets REALLY slow once you hit big numbers (like a million). So I wrote a generator that will go through all the numbers to n, generating them from primes instead of finding the primes from the number.

for factors, number in prange(1000) : # do something with factors and number primeRange = itertools.imap(lambda x : (tuple(util.primeFactor(x)), x), xrange(2, 10)) # Same thing in different order range(2, 1000) == prange(1000) # False set( range(2, 1000) ) == set( prange(1000) ) # True

And finally the prange function:

def prange(n) : """ prange(n) -> generator Returns a generator for numbers from (2 to n-1) in prime base order e.g. [x[1] for x in prange(10)] = [2, 3, 5, 7, 4, 6, 9, 8] ignoring order this is a complicated way to get a range e.g. set([x[1] for x in prange(1000)]) == set(range(2, 1000)) The first term is a tuple (primes, powers) where len(primes) == len(powers) e.g. [x[0] for x in prange(10)] = [(2,), (3,), (5,), (7,), (2, 2), (2, 3), (3, 3), (2, 2, 2)] And to make sure the sums are right. [prod(p) for p in [x[0] for x in prange(1000)]] == [x[1] for x in prange(1000)] """ for count in itertools.count(1) : done = True for d, comb in primeLists(lambda : util.primes(), count, n) : done = False yield comb, d if done : break def prod(list) : return reduce(operator.mul, list) def pow(a, b) : return prod( [ a[i] ** b[i] for i in xrange(min(len(a), len(b)))] ) def powers(comb, lim) : def iterFunc() : for c in itertools.count(1) : yield c return walkIters(iterFunc, len(comb), lambda nums : pow(comb, nums), lim) def primeCombinations(primeFunc, count, lim) : return walkIters(primeFunc, count, prod, lim, alwaysAscending = True) def primeLists(primeFunc, count, lim) : return walkIters(primeFunc, count, prod, lim, alwaysAscending = True, allowDuplicated = True) def walkIters(generator, count, evalFunc, lim, alwaysAscending = False, allowDuplicated = False) : """ walkIters(iterFunc, count, evalFunc, lim, alwaysAscending = False) -> walks an iterator returning a tuple of (evalFunc(ret), ret) for each row, where ret = (iterval0, iterval1, ...) and it is guarenteed that evalFunc(ret) = 0 : if alwaysAscending : for i in xrange(pos + 1, count) : if allowDuplicated : while nums[i] < nums[i-1] : nums[i] = iters[i].next() else : while nums[i] <= nums[i-1] : nums[i] = iters[i].next() d = evalFunc(nums) if d < lim : yield (d, tuple(nums)) pos = count -1 nums[pos] = iters[pos].next() else : if pos == 0 : break pos -= 1 nums[pos] = iters[pos].next() for num in xrange(pos+1, count) : iters[num] = generator() nums[num] = iters[num].next()

Or if you need the primes in order of unique prime factors:

def prangePrimeOrder(n) : """ prange(n) -> generator Note: This is about 2x slower than prange(n) so if you don't care about order, use prange() Returns a generator for numbers from (2 to n-1) in prime base order e.g. [x[1] for x in prange(10)] = [2, 4, 8, 3, 9, 5, 7, 6] ignoring order this is a complicated way to get a range e.g. set([x[1] for x in prange(1000)]) == set(range(2, 1000)) The first term is a tuple (primes, powers) where len(primes) == len(powers) e.g. [x[0] for x in prange(10)] = [((2,), (1,)), ((2,), (2,)), ((2,), (3,)), ((3,), (1,)), ((3,), (2,)), ((5,), (1,)), ((7,), (1,)), ((2, 3), (1, 1))] which says [2^1, 2^2, 2^3, 3^1, 3^2, 5^1, 7^1, 2^1 * 3^1] If you want it paired in the other direction e.g. [zip(z[0], z[1]) for z in [x[0] for x in prange(10)]] = [[(2, 1)], [(2, 2)], [(2, 3)], [(3, 1)], [(3, 2)], [(5, 1)], [(7, 1)], [(2, 1), (3, 1)]] """ for count in itertools.count(1) : done = True for d, comb in primeCombinations(lambda : util.primes(), count, n) : done = False for pownum, nums in powers(comb, n) : yield (comb, nums), pownum if done : break

If anyone can speed up my code, please submit any changes. And feel free to use the code however you see fit. BSD License.

## Leave a Reply