Euclidean Algorithm   유클리드 알고리즘

1. 유클리드 호제법/알고리즘 (Euclidean Algorithm)

  ㅇ 두 정수의 최대공약수를 빠르게 계산해내는 알고리즘

  ㅇ 최대공약수를 구하는 통상적인 방법으로는,
     - 두 수를 소인수분해한 후, 그 중 공통되는 소수 중 제일 큰 것을 찾아가는 복잡한 방법을 씀
     - 그러나, 소인수분해(어떤 수를 소수의 곱셈 형태로 인수분해하는 것) 자체도 쉽지 않음
     - 또한, 두 약수 리스트 중 공통으로 들어있는 제일 큰 수를 찾는 것도 만만치 않음


2. 유클리드 호제법/알고리즘의 표현

  ㅇ 두 수의 나눗셈을 반복하여 나머지가 0이 될 때 최대공약수가 구해지는 방법

  ㅇ 例) gcd(21,9) → a = 21, b = 9
     -  a  = b x q + r                          ☞ 나눗셈 관계식 참조
     -  21 = 9 x 2 + 3 → b = 9, r = 3
        . 여기서, 나온 나머지 3으로, 방금 나누어지는데 사용된 수 9를 나눔
     -   9 = 3 x 3 + 0 → b = 3, r = 0  (나누어떨어짐)
        . 여기서, 나머지가 0이 되므로, 이때 나누는 수 3이 최대공약수가 됨
     -  따라서, gcd(21,9) = 3

  ㅇ 알고리즘 표현 형태
       
ㅇ 입력 : r[0], r[1]
ㅇ 출력 : gcd ( r[0], r[1] )

Euclidean ( r[0], r[1] ) {
    초기화 : i = 1 ;
    while ( r[i] ≠ 0 ) {
       r[i] = r[i-2] mod r[i-1] ; 
    }
    return gcd ( r[0], r[1] ) = r[i-1]
}
 

  ※ 결국, 유클리드 알고리즘은,
     - 단순히 나눗셈 만 되풀이하는 것 만으로도 최대공약수가 구해지게 됨
        . 즉, 나눗셈을 되풀이하다가 마지막에 나누어떨어질 때,
        . 그 때 나누는 수가 최대공약수가 됨

  ※ 한편, 마지막이 1이 되는 경우(즉, 두 수의 최대공약수가 1 인 경우)에, 
     - 이 때의 두 수는 서로소(Relatively Prime) 라고 함