최대 공약수, 공배수 구하기 // 코테

두 정수 a 와 b 가 있다

 

 

 - 최대 공약수

유클리드 호제법에 따라

 

a와 b의 최대 공약수는 b와 a%b 의 최대 공약수와 같다 ( 단, a%b가 0이라면, b가 a와 b의 최대공약수가 된다. )

 

따라서

다음과 같은 형태로, a%b가 0이 될 때 까지 반복시키고 a를 구하면 최대 공약수를 구할 수 있다

 

 - 최소 공배수

두 수의 곱에 최대 공약수를 나누면 최소 공배수를 구할 수 있다

 

최소 공배수 = a * b / gcd (a,b)