알고리즘
-
유클리드 호제법 정리알고리즘 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)의 값이 그 두 수의 최대공약수이다. 내가 이해한 바로 이 유클리드 호제법이 가능한 근본적인 이유는 b mod a가 0이라면, 즉 a로 b를 나눌 수 있다면, 반드시 a가 최대공약수이기 때..