Wednesday, April 15, 2015

Project Euler #5 - 20 이하의 모든 자연수로 나누어지는 최소의 숫자

Smallest multiple - 20 이하의 모든 자연수로 나누어지는 최소의 숫자

크게 어렵지 않으니 그냥 계산하면 된다
2*2*2*2*3*3*5*7*11*13*17*19 = 232792560


괜히 어렵게 문제를 풀어보면..
20까지의 숫자를 소인수 분해하고, 그 결과 지수들의 최대값을 찾고, 최소공배수를 찾아보자.

def chk_pn(n,pn):
    for p in pn:
        if n % p == 0: return False
        if p**2 > n: return True

def inc_pn(pn):
    n = pn[-1] + 2
    while True:
        if chk_pn(n,pn): pn.append(n); return pn
        n += 2

def factor(n,pn):
    # n > 2
    i, fDic = 0, {}
    while True:
        p = pn[i]
        if p == pn[-1]: pn = inc_pn(pn)
        if n % p == 0:
            if p in fDic: fDic[p] += 1
            else: fDic[p] = 1
            n /= p
            i -= 1
        i += 1
        if pn[i]**2 > n:
            if n in fDic: fDic[n] += 1
            else: fDic[n] = 1
            return fDic

pn, SCM = [2,3], {}
for i in range(4,21):
    fDic = factor(i,pn)
    for k in fDic:
        if k in SCM: SCM[k] = max(SCM[k],fDic[k])
        else: SCM[k] = fDic[k]

op = 1
for x in SCM:
    op *= x**SCM[x]

print op

좀 부끄러운 지저분한 코드지만 답은 잘 나온다. 
마찬가지로 from sympy import factorint 를 이용하면 삽질을 줄일 수 있다.

No comments: