문제

두 수를 입력받아 최대공약수(GCM)를 구하는 프로그램을 작성하시오.

입력

두 자연수 a, b

출력

최대 공약수(GCM)

24 9

3

힌트

두 자연수의 최대공약수(GCM) 구하는 방법

a. 두 자연수 중에서 큰 수를 작은 수로 나눈 나머지가 0이라면 GCM은 나눈 수(작은 수) 이다.

예) 자연수 24와 6의 GCM : mod(24, 6) = 0 ⇒ 나머지가 0이므로 작은 수 6이 GCM이다.

b. 두 자연수 중에서 큰 수(제수)를 작은 수(피제수)로 나눈 나머지가 0이 아니라면 나눈 수를 제수로 치환하고 나머지를 피제수로 치환하여 나머지를 구하는 방법으로 나머지가 0이 될 때 까지 수행하여 나머지가 0으로 떨어질 때의 제수가 두 자연수의 GCM이다.

예) 자연수 24와 9의 GCM

1회. mod(24, 9) = 6 : 나머지가 0이 아님

2회. mod(9, 6) = 3  : 1회의 피제수 9를 제수로 나머지 6을 피제수로 치환 ⇒ 나머지가 0이 아님

3회. mod(6, 3) = 0  : 2회의 피제수 6을 제수로 나머지 3을 피제수로 치환 ⇒ 나머지가 0

⇒ 나머지가 0으로 떨어진 3회의 피제수 3이 GCM이다.

출처

내가쓴 보조자료-알고리즘