Project Euler 5 solution and explanation.

euler5.py

"""Project Euler: Problem 5
Requires: Python 2

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?

This result takes a different approach to factoring than we used in class.
The code that we built is in another gist linked in the email that I sent
out. I didn't feel the need to generate prime numbers if I could let a prime
factorization method take care of that for me.

I used `prime_factors_of` to return a dict of prime factors comprising an
argument. This is exactly like what we did on the whiteboard in class today
for each number. For example:

    2: 2
    3: 3
    4: 2 * 2
    5: 5
    6: 2 * 3

After building such a dict for each number between two and twenty, I built a
new dictionary that kept track of the most frequent factor, and stored that
for a given factor. This is essentially the "cancelling out" phase that we
went through on the whiteboard. The prime factors of four don't matter due
to eight.

Once this new dict of the highest frequency factors was constructed, I built
a product accumulator to multiply by the factors, providing me with my answer.

Look through the code, we'll discuss it in more depth tomorrow, and suggest
changes or optimizations. Read the code, run the code. Gather questions for
tomorrow and try experimenting with some of the new concepts presented in your
REPL (Python interpreter).
"""


def prime_factors_of(num):
    """Returns a dict of a given integers prime factors.

            Example: prime_factors_of(20) => {2: 2, 5: 1}
            Indicates that two twos and a five are the factors.
    """
    if num == 0:
        return {0: 0}
    elif num == 1:
        return {1: 1}

    result = {}

    for ix in range(2, num + 1):
        # This is the idiom that reminds me of Euler #3...
        while num % ix == 0:
            num /= ix

            # You've not likely seen this. We are adding (or updating) an
            # entry in the result dict, incrementing the value if one exists
            # The dict.get() method attempts a lookup on the first argument,
            # 'ix'. If the key does not exist (lookup fails), then the second
            # argument is used as the return from the lookup. If no key 'ix'
            # exists at the point of assignment, we will increment a default
            # value of 0, setting new entries to 1 and incrementing existing
            # entries. For more info: help(dict)
            result[ix] = result.get(ix, 0) + 1

    return result


def product(num_list):
    """Like `sum`, but for multiplication"""
    def mult(x, y):
        # Just a helper function so that I don't have to use an ugly lambda
        # Also to point out (again) that we can have nested functions
        return x * y

    # Applies the given function, `mult`, to the given list, 'num_list'
    # [A, B, C] => ((A * B) * C)
    return reduce(mult, num_list)


if __name__ == '__main__':
    result = {}

    # First, we build a collection of those factors that are most numerous from
    # the prime factorizations in a dictionary
    for ix in range(2, 20 + 1):
        # dict.items() returns a tuple pair of the key and value for
        # each key value pair in the dict that is iterable
        # {x: y, r: 3}.items() => (x, y), (r, 3)
        for factor, frequency in prime_factors_of(ix).items():
            # Using the `get` method again. If 'factor' doesn't appear as a key
            # in 'result', we compare the frequency of that factor to zero,
            # ensuring that the new factor is added to 'result'. If the factor
            # does exist, we only update the frequency for that factor if the
            # new frequency is greater.
            if result.get(factor, 0) < frequency:
                result[factor] = frequency

    # Now that we have a dictionary of the most frequent factors, we multiply
    # our multiple by each factor raised to its frequency to produce an answer.
    multiple = 1
    for factor, frequency in result.items():
        multiple *= factor ** frequency

    print multiple