I have implemented a solution to Project Euler problem 5:2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.  What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?My solution uses Python 2.7, and consists of a module I created that finds prime factors of numbers - the factorization module. It contains the functions factors() and primegen() which are implemented in the eponymous Python source files. At the top level of the project, I define a function smallest_multiple() that uses factors() and in that same file a main() function to drive it.factorization module:primegen.py:import itertoolsdef 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()factors.py:from factorization.primegen import primegendef 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 nTop-level:e5.py:#!/usr/bin/env pythonfrom factorization.factors import factorsdef 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 resultdef main():    print('result = {0}'.format(smallest_multiple(20)))if __name__ == '__main__':    main()The entire project can be found on Github. Its only additions are a Sublime Text 2 project and some scripts to enable running the doctests from within the editor.I do have some specific concerns about this code. I find that smallest_multiple() is weird and clunky - especially iterating through each element of factors and asking for its count. It seems there should be some more elegant way to aggregate the factors and their exponents. I wonder if my docstrings and doctests are reasonably correct, and if my module organization is coherent. I'm also wondering if I'm abusing generators, particularly in the doctests where I call list() on each generator to get the result, and the nested generator functions in primegen().Generally, I'd also like feedback on how Pythonic this code is. I've tried to keep PEP 8 in mind, but any deviations I've hastily overlooked would be good to know about. I also didn't do much in terms of input validation and robustness, so general advice on the idiomatic ways of doing so would be appreciated.
Project Euler #5 (LCM of [1, 2, , 20])
python;programming challenge;primes
Let me put what @tokland said in another way. In the Zen of Python there is a sentence If the implementation is hard to explain, it's a bad idea.. The same thing that you are doing can be done much more efficiently and clearly by changing the algorithm used. Unless you wanted to make a prime generator for some other thing and used this exercise as an excuse to get on with making it, using prime generation here is a bad idea. Bad according to Python's readability view because Simple is better than complex.. For efficiency just try running your code and this code for 1000.Now getting with your code itself. primegen.pyWhy didn't you make the generate_primes as your top level function with a nested next_p? For all intents and purposes it is doing everything. The initialization of marked could have been easily done inside the function and it would have become a lot clearer what you are doing. Currently you are returning a generator from the function call which is yielding required values while you could have directly called the generator itself which would have yielded values. There is an unnecessary level of indirection here.factors.pyThe calculation of square root should have been done before the loop. It is calculated at every iteration of the loop while it is actually used once as the function being called here is a generator. That's what I thought when I saw your code the first time. Ignore that because that's not happening here. Just telling you what kind of confusion you have created in primegen.pyJust to be clear, nested generators aren't the problem here.If you are writing for efficiency alone then while not n%p is perfectly ok. Go for while n % p != 0 if you want a middle ground between efficiency and readability.For readability while n % p is not 0 is the preferable one. Its basically English. As has been said in the comments, this isn't the correct way to do it.I am leaving the top module for now. Myabe review it later.I hope this helps.