크게 어렵지 않으니 그냥 계산하면 된다
2*2*2*2*3*3*5*7*11*13*17*19 = 232792560
괜히 어렵게 문제를 풀어보면..
20까지의 숫자를 소인수 분해하고, 그 결과 지수들의 최대값을 찾고, 최소공배수를 찾아보자.
좀 부끄러운 지저분한 코드지만 답은 잘 나온다.
마찬가지로 from sympy import factorint 를 이용하면 삽질을 줄일 수 있다.
오일러 프로젝트 projecteuler.net 의 문제들을 풀고 설명하는 스터디 공간입니다. 조언, 부연, 비판, 질문 환영합니다.
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
No comments:
Post a Comment