Project Euler: Problem 5

http://projecteuler.net/index.php?section=problems&id=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?

Thinking about this for a few minutes, the solution will be the product of the minimal set of prime factors needed to produce each possible value from 1 to n (in our case, n=20). Let's recycle that factorization code we wrote for p003 and add a little somethin' somethin'.

def f1(n):
    factors = {}

    for i in xrange(2, n+1):
        # Recycle factoring code from p003
        primes = []
        last = i

        while last != 1:
            try:
                c = primes[-1]
            except:
                c = 2

            while last % c != 0:
                if c==2:
                    c += 1
                else:
                    c += 2

            primes.append(c)
            last /= c

        # Iterate through the factors and group/accumulate
        for p in primes:
            c = primes.count(p)

            # Keep track of the least amount of factors needed
            if c > factors.get(p,0):
                factors[p] = c

    # Multiply together the minimal set of primes
    results = 1
    for p,c in factors.iteritems():
        results *= p**c

    return results

On my set-up, f1(20) returns in about 8.53e-05 seconds.

Something interesting: I investigated using the built-in SET object to get a unique list of members in 'primes'. That was actually slightly slower than simply iterating over all members in 'primes'. It would likely be quicker for larger, more redundant lists.