khp blog

유클리드 호제법 2개의 수의 최소 공약수를 계산할 때 큰 수(a)를 작은 수(b)로 나누고, 나머지(r)가 0이 아니면 나누었던 수(b)를 나머지(r)로 다시 나누고 나머지가 0이 될때까지 반복합니다. 반복 하다가 나머지가 0이 될때 나눈 수가 최소 공약수가 됩니다. 예를 들어 78696과 19332의 최대공약수를 구하면, 78696 ＝ 19332×4 ＋ 1368 19332 ＝ 1368×14 ＋ 180 1368 ＝ 180×7 ＋ 108 180 ＝ 108×1 + 72 108 ＝ 72×1 ＋ 36 72 ＝ 36×2 36이 최소 공배수입니다. 최대 공약수(gcd, greatest common divisor) 최대 공약수를 계산하는 여러가지 방법이 있겠지만 유클리드 호제법 을 사용하여 계산하는 것이 코드도 간결..