bitCode 문제정보
1s 128MB
문제
유클리드 호제법은 2개의 자연수의 최대 공약수를 구하는 알고리즘입니다. 호제법이란 두 수가 서로 상대방 수를 나누어 원하는 결과를 얻는 방법을 말합니다. 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 한다면, a, b의 최대 공약수는 b와 r의 최대 공약수가 됩니다. 또, b를 r로 나눈 나머지를 r1이라고 한다면, a, b의 최대 공약수는 r, r1의 최대 공약수와 같습니다. 이 과정을 반복해 나머지가 0이 되면, 이때 나누는 수가 최대 공약수가 됩니다. 이를 이용하여 a, b의 최대 공약수를 구하는 프로그램을 작성해 봅시다.
입력형식
첫 줄에 자연수 a, b가 입력됩니다. (1≦a,b≦100)
출력형식
a, b의 최대 공배수를 출력하시오.
힌트
유클리드 호제법은 컴퓨터를 이용하여 최대 공약수를 간단히 구할 수 있습니다.
이때 a와 b중 나누는 수와 나누어지는 수로 선택해야하는지를 고민할 수 있습니다. 하지만 그 순서는 크게 상관이 없습니다.
12 % 16 = 12 가 됩니다. 따라서 다음 계산은
16 % 12 = 4 가 됩니다.
12 % 4 = 0 이 되며
나머지가 0이 되었으므로 이때 나누는 수 4가 최대 공약수가 됩니다.
코드는 다음과 같습니다.
이때 a와 b중 나누는 수와 나누어지는 수로 선택해야하는지를 고민할 수 있습니다. 하지만 그 순서는 크게 상관이 없습니다.
12 % 16 = 12 가 됩니다. 따라서 다음 계산은
16 % 12 = 4 가 됩니다.
12 % 4 = 0 이 되며
나머지가 0이 되었으므로 이때 나누는 수 4가 최대 공약수가 됩니다.
코드는 다음과 같습니다.
while(b!=0){
c = a%b
a = b
b = c
}
이때 답은 a가 됩니다. 예시 1
입력예시
97 27
출력예시
1