[프로젝트 오일러] Problem 5 Solution

프로젝트 오일러라는 사이트는 적당한 수학? 아이디어? 생각? 들을 배울 수 있는 사이트입니다.

http://euler.synap.co.kr/

Project Euler

사이트에 대한 자세한 내용은 위 링크로 들어가셔서 한번 보시면 될 것 같습니다.

 

문제 내용

5번 문제는 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수를 구하는 문제입니다.

 

풀이

먼저 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수를 수학적으로 접근해보면 무엇을 의미하는지 생각해보아야 합니다. 이 말은 좀더 수학적으로 접근해본다면 1부터 20까지 수의 최소공배수을 의미합니다.

 

그리고 여러 수의 최소공배수를 구할 때는 아래와 같은 아이디어들이 사용됩니다.

 

1. "a와 b의 최소공배수"와 "c" 의 최소 공배수는 a와 "b와 c의 최소공배수"의 최소 공배수와 같다.

2. a x b / (a와 b의 최대공약수) 는 (a와 b의 최소공배수)이다.

 

위의 아이디어를 활용해 python 코드를 작성하면 아래와 같습니다.

 

def gcd(a,b):
    return gcd(b,a%b) if b>0 else a

n = 20
ans = 1
for i in range(2,n+1):
    ans = ans*i // gcd(ans,i)

print(ans)

 

답은 스스로 한번 코드를 작성하고 실행해보시길 바랍니다 :)

Rmx