유클리드 호제법

유클리드 호제법이란 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나이다.

 

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 의미한다.

 

1071와 1029의 최대 공약수를 구해보자.

1071 = 1029*1 + 42

1029 = 42*24 + 21

42 = 21*2 + 0

따라서 최대공약수는 21이다.

 

a,b는 Z에 속해있고 a를 b로 나눈 나머지가 r이라고 하자(여기서 a>=b이고 r은 0<=r<b)

a와 b의 최대공약수를 (a,b)라고 하면, (a,b)=(b,r) 이 식이 성립하고 위의 예시를 이용하면 (1071,1029)=(1029,42)=(42, 21)=(21,0)=21처럼 쓸 수 있다.

 

알고리즘

1. 입력값 M, N (M>N)

2. N이 0이라면 M을 출력하고 종료

3. M이 N으로 나누어 떨어지면 N을 출력하고 종료

4. 나누어 떨어지지 않으면 그 나머지를 M에 대입하고 M과 N을 바꾼뒤 알고리즘 반복한다.