Project Euler Problem 005

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?

たぶん1から20までの数の最小公倍数を聞かれているのだと思う。

最小公倍数の求め方はよく分からなかったので、全部の数字を素因数分解してそれぞれ素数がいくつずつ必要なのかをカウント、それを全部積算した。

import math

def primefactors(n):
    result = []
    
    while n and not n & 0x01:
        n >>= 1
        result.append(2)
    
    m = 3
    limit = math.sqrt(n)
    while n > 1 and m <= limit:
        while n % m:
            m += 2
        else:
            while True:
                n /= m
                result.append(m)
                if n % m: break
            limit = math.sqrt(n)
    else:
        if n != 1:
            result.append(n)
            
    return result

N = 20

d = {}
for i in xrange(N, 1, -1):
    x = primefactors(i)
    for j in set(x):
        cnt = x.count(j)
        if d.get(j, 0) < cnt:
            d[j] = cnt
print d

result = 1
for k, v in d.iteritems():
    result *= math.pow(k, v)
    
print result

答え: 2^4 * 3^2 * 5^1 * 7^1 * 11^1 * 13^1 * 17^1 * 19^1 = 232792560