问项目Euler #5 (LCM of [1，2，…])，20])

EN

import itertools

def primegen(upper):
    """Return generator yielding all primes less than upper 
    >>> list(primegen(10))
    [2, 3, 5, 7]
    >>> list(primegen(30))
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """

    # http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    marked = [False] * (upper - 2)

    # using generator here lets us lazily evaluate whether
    # a number has been marked
    def next_p():
        for i,v in enumerate(marked):
            if not v:
                yield i

    def generate_primes():
        for p_idx in next_p():
            p = p_idx + 2
            cursor = p
            while True:
                cursor = cursor + p
                try:
                    marked[cursor-2] = True
                except IndexError:
                    break
            yield p

    return generate_primes()

from factorization.primegen import primegen

def factors(n):
    """generator function yielding the prime factors of n
    Heavily derived from http://en.wikipedia.org/wiki/Trial_division
    >>> list(factors(14))
    [2, 7]
    >>> list(factors(13195))
    [5, 7, 13, 29]
    >>> list(factors(8))
    [2, 2, 2]

    """

    for p in primegen(int(n**0.5) + 1):
        # sqrt(n) < p => n = q * (p^k), where k is 0 or 1, and q is product of each element of factors
        if p*p > n:
            break
        # append factor for each time it appears
        while not n%p:
            yield p
            n = n / p
    if n > 1:
        yield n

#!/usr/bin/env python

from factorization.factors import factors

def smallest_multiple(n):
    """Returns smallest multiple evenly divisble by each 1..n in N

    >>> smallest_multiple(10)
    2520

    """

    # for each number <= n, find its prime factors p1^k1, p2^k2, ...
    #   store as prime => exponent
    #       replace existing stored exponents only if the replacement is greater
    # for each prime=>exponent
    #   result = result * prime^exponent
    factor_exp_map = {}
    for i in xrange(n,0,-1):
        facs = list(factors(i))
        for factor in facs:
            fact_count = facs.count(factor)
            cur_fact_count = factor_exp_map.get(factor,0)
            if (fact_count > cur_fact_count):
                factor_exp_map[factor] = fact_count
    result = 1
    for factor, exponent in factor_exp_map.iteritems():
        result = result * factor**exponent
    return result

def main():
    print('result = {0}'.format(smallest_multiple(20)))

if __name__ == '__main__':
    main()