최대 공약수 찾는 알고리즘(유클리드의 알고리즘(Euclid's algorithm))

최대 공약수는

A=G*a

B=G*b

로 표현이 가능합니다. 

그렇다면 두 수를 빼보면

A-B=(a-b)G

로 표현이 가능합니다.

그럼 만약 최대 공약수를 구하는 함수 X가 있다고 하면

X(a,b) 와  X(a-b,b) (a>b) 의 값은 같게 나오게 됩니다.

그리고 X(0,b)가 된다면 b가 최대 공약수가 되고

X(a-b,b) (a<b)가 된다면 a-b가 음수가 되기때문에 이 경우에는 빼지 말고 a와 b의 위치를 서로 바꿔주어야 합니다.

아래 예시입니다.

(110,33) = (77,33)

               (44,33)

               (11,33)  // 여기서 두 수 교환 (33,11)

               (22,11)

               (11,11)

               (0,11)  //0이 나왔기때문에 최대 공약수는 11

이 됩니다.

아래 프로그램은 이를 이용한 프로그램입니다.

사실 이 알고리즘을 개선시킨 알고리즘이 있습니다.

그 알고리즘은 다음 포스팅에서 소개하도록 하겠습니다.

오타나 지적 환영합니다. ^^