[STUDY] 유클리드 호제법

이 포스팅은 유클리드 호제법을 공부하고 나서 백준문제를 해결하고 정리를 위해 올리는 글입니다.

 

유클리드 호제법은 최대공약수,최소공배수를 쉽게 구할 수있는 공식들 중에 하나이다.

방법은 또 매우 간단한데,

 

최대공약수를 구하기 위해서

예를들어 A와 B라는 수가 각각 주어진다면 최대공약수를 구하기 위해서는 AxB를 Bx(A%B)로 나눠주고

나온 나머지를 r이라고 할때 r이 0이 아니라면, 이를 다시 두번째 항 (Bx(A%B))과 나머지 연산을 해서 r을 또 구하고..

이게 다시 0이 아니라면 또 다시 두번째 항과 나눠주고.. 

 

이것을 반복해서 나머지가 0인 값이 최대공약수가 된다.

 

최소공배수는 여기서 구한 최대공약수를 이용해서 아주 쉽게 구할 수 있다.

a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다