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.