最小公約数

Project Euler 5

2520 は 1 から 10 までの数で割り切ることができる最小の数である。
1 から 20 までの数で割り切ることができる最小の値は何か？

---

もっとも単純なのがユークリッドの互除法を用いて最小公倍数を求める方法である。
x, y の最小公倍数は、最大公約数 L を用いて、x $\times$ y / $\lfloor$L$\rfloor$ で算出することができる。

# SAMPLE_1


def gcd(x, y):
    if y != 0:
        return gcd(y, x % y)
    return x


def lcm(x, y):
    return (x * y) // gcd(x, y)

N = 20

ans = 1
for n in range(2, N + 1):
    ans = lcm(ans, n)
print ans

また、Project Euler 3と同様、素因数分解する方法でも算出してみた。
各素数のべき乗数の最大値を集約し計算する。

# SAMPLE_2
from math import sqrt


def f(x, n):
    r = 0
    while x % n == 0:
        x /= n
        r += 1
    return x, r


def integer_factorization(n):
    ans = {}
    n0 = n

    n0, r = f(n0, 2)
    if r != 0:
        ans[2] = r

    i = 3
    while(i < int(sqrt(n)) + 1):
        n0, r = f(n0, i)
        if r != 0:
            ans[i] = r
        i += 2
    if n0 != 0:
        ans[n0] = 1
    return ans

N = 20
ans = {}
for i in range(2, N + 1):
    dic = integer_factorization(i)
    for j in dic.keys():
        try:
            ans[j] = max(ans[j], dic[j])
        except KeyError:
            ans[j] = dic[j]

r = 1
for i in ans.keys():
    r *= i ** ans[i]
print r