1최대공약수 알고리즘

 

최대공약수의 성질을 떠올리면서 다음 알고리즘을 생각해 봅시다.

 

1 | 두 수 중 더 작은 값을 i에 저장합니다.

2 | i가 두 수의 공통된 약수인지 확인합니다.

3 | 공통된 약수이면 이 값을 결괏값으로 돌려주고 종료합니다.

4 | 공통된 약수가 아니면 i를 1만큼 감소시키고 2번으로 돌아가 반복합니다(1은 모든 정수의 약수이므로 i가 1이 되면 1을 결괏값으로 돌려주고 종료합니다).

 

예를 들어 4와 6의 최대공약수를 찾으려면 다음과 같은 과정을 거칩니다.

 

1 | i에 4를 저장합니다(4와 6 중 작은 값인 4가 최대공약수 후보 중 가장 큰 값).

2 | 4는 i로 나누어떨어지지만, 6은 나누어떨어지지 않습니다.

3 | i를 1만큼 감소시켜 3으로 만듭니다.

4 | 4는 i로 나누어떨어지지 않습니다.

5 | i를 1만큼 감소시켜 2로 만듭니다.

6 | 4도 i로 나누어떨어지고 6도 i로 나누어떨어지므로 i 값 2가 최대공약수입니다.

 

이 알고리즘을 프로그램으로 만들면 다음과 같습니다.