Anonymous

# Project Euler #5

# generate prime factor tree for each number then multiply the highest order
# prime term for each prime together to get LCM

from collections import defaultdict
pfreqs = defaultdict(int)

from common import primes
plist = primes(20) # primes to 20

# obviously no need to include 1-10
numbers = range(11,21)

# generate our frequency table
for n in numbers:
    ptree = defaultdict(int)
    for p in plist:
        while n % p == 0:
            ptree[p] += 1
            n = n / p
    for p in ptree:
        if ptree[p] > pfreqs[p]:
            pfreqs[p] = ptree[p]

# product of prime^order for all primes in frequency table
print reduce(lambda x,y:x*y, [ p**pfreqs[p] for p in pfreqs ])