# Project Euler #5 (LCM of [1, 2, …, 20])

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 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()


factors.py:

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


Top-level:

e5.py:

#!/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()


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.

• The problem with your approach is on the maths side: you are being asked, with other words, what's the least common multiple of range (1..20) – tokland Nov 17 '13 at 0:09
• @tokland Thanks. To be clear, I don't believe there is any trouble with this code doing what I want - the program successfully answered the problem. I'm looking for a code review. – Carl Veazey Nov 17 '13 at 5:18
• Carl Veazy Have a look at J.F.Sebastian's answer to this SO question to see what tokland means. – steenslag Nov 17 '13 at 15:23
• @steenslag thanks - solved the problem on paper first using prime factorization so hadn't thought to investigate a different approach. I appreciate the explanation! – Carl Veazey Nov 18 '13 at 2:10

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.py
Why 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.py
The 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.py

Just 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.

• Thanks for your feedback! When I figured out lcm by prime factorization I ended up re using the factorization code from a previous problem hence them being in their own module. Hadn't thought to pursue a different algorithm but research shows you're right. Could you clarify a bit about the square root comments - and particularly the "ignore that" comment? – Carl Veazey Nov 18 '13 at 2:08
• " while n % p is not 0": no. is tests identity, not equality, and should never be used for numerical comparisons. – DSM Nov 18 '13 at 3:01
• @DSM Yeah, it checks for identity but if just used for numbers then it will give the same results as equality. For objects (and hence composite data types) it should not be used as equality. Here the check is for numbers only. So is that still a problem? – Aseem Bansal Nov 19 '13 at 14:50
• is only works for a certain range of small integers (try 501 is 500+1 for a counter-example), and even that is an implementation detail of CPython. – Janne Karila Nov 20 '13 at 13:40
• @CarlVeazey The ignore that line (now struck through) was what I had thought when I first saw your code. But my thought was incorrect and your code was correct. I added my incorrect thought to show that the code's design could create confusion. That or maybe I am just a Python noob :) – Aseem Bansal Nov 21 '13 at 16:51

It's pretty good Python. My opinions are:

• It might be slightly over-engineered. For a small problem like this, simplicity would be preferable to scalability. For example, you could do without the Sieve of Eratosthenes.
• Gathering repeated prime factors into exponents should probably be considered the responsibility of the factors() function.
• Your code would be more compact if you used a more functional (instead of procedural) style, and clearer if you used more mathematical vocabulary (e.g. "product" and "least common multiple").

A previous review illustrates these principles.

• I did re-use some code for another prime generation hence the presence of the sieve and the over-engineering. Could you explain what you mean a 'functional' approach? Could you give a specific example? – Carl Veazey Nov 20 '13 at 4:55
• Functional programming in 600 chars? Start with examples. Think in big-picture terms of pushing data through transformations. Use list comprehensions, recursion, lambda, map(), filter(), reduce(). Pass functions as parameters to functions. Avoid mutation (assigning a value to a variable then changing it) and loops. Read and do sicp (chapters 1 and 2). Realize the limits of functional programming in Python. – 200_success Nov 20 '13 at 6:36

A couple of things that stick in my eye:

1. Each call to factors runs the sieve of Eratosthenes again from scratch.
2. This...

cursor = p
while True:
cursor = cursor + p
try:
marked[cursor-2] = True
except IndexError:
break


...is a rather clunky substitute for a for loop like this:

for cursor in xrange(2*p-2, len(marked), p):
marked[cursor] = True