호제 (백준 2609 최대공약수와 최소공배수, 1934 최소공배수 C++)

 

 

백준 2609 최대공약수와 최소공배수를 풀었다

아 뭐야 완전 쉽네~하고 그냥 뒤로 갈라는데 갑자기 싸했다

나는.. 이걸 뭔가 비효율적으로 풀 것만 같은 느낌?

그래서 그냥 바로 솔루션을 찾아봤다 (풀라면 풀 문제니까)

 

유클리드 호제법이란걸 500만년 만에 들었다

그래.. 이런게 었었지..

 

유클리드 호제법

n, m 두 자연수가 주어졌을 때 gcd(n, m) = gcd(m, n% m)이다 (gcd = 최대공약수)

따라서 n%m이 0이 될 때까지 반복하면 최대공약수를 찾을 수 있다

최소공배수는 n*m/gcd(n, m)이다