➗ 유클리드 호제법
나누고, 나누고,
또 나누면 최대공약수
두 수의 최대공약수(GCD)를 구할 때 약수를 일일이 찾을 필요 없어요. 큰 수를 작은 수로 나눈 나머지로 계속 바꿔가기만 하면, 결국 최대공약수에 도달해요. 2300년 전 유클리드가 정리한 방법이에요.
규칙: (a, b)에서 a를 b로 나눈 나머지를 r이라 하면, gcd(a,b) = gcd(b,r)이에요. r이 0이 될 때까지 이걸 반복하면, 마지막 0이 아닌 수가 바로 최대공약수예요.