-
유클리드 호제법 정리알고리즘 2024. 1. 19. 15:55
1. 최대 공약수 구하기
6과 8의 최대 공약수 구하기 예시
public int GCD(){ int a = 8 int b = 6 int r = 0; while (b!=0) { r = a%b; a = b; b = r; } return a; }
유클리드 호제법에서 최대공약수는 다음과 같다.
2개의 자연수 a, b(a > b)에 대해서 a를 b로 나눈 나머지가 r일 때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
작은 수(b)를 계속해서 나눈 나머지인 작은 수는 결국 0에 도달 할 수 밖에 없는데, 그때 큰수(a)의 값이 그 두 수의 최대공약수이다.
내가 이해한 바로 이 유클리드 호제법이 가능한 근본적인 이유는
가 0이라면, 즉 a로 b를 나눌 수 있다면, 반드시 a가 최대공약수이기 때문이다.
ex) 0과 2 , 1과 2, 3과 6 을 생각할때 나머지가 0이라면 반드시 최대 공약수가 될 수 있다.
그렇지 않으면, GCD(a, b)는 GCD(b, a mod b)와 반드시 동일하다.}
2. 최소 공배수 구하기
위에서 배운 최대 공약수를 다시 이용한다.
public int Main(){ int a = 8 int b = 6 int copy_a = a; int copy_b = b; int r = 0; while (b!=0) { r = a%b; a = b; b = r; } return copy_a * copy_b / a; }
두 수 a와 b(a>b)의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 것과 같다.
더 자세하게 공부하고싶다면 위키백과의 증명을 찾아보는것이 좋다.
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95