프로그램 명: euclid
제한시간: 1 초
두 수를 입력받아 최대공약수,최소 공배수를 구하는 프로그램을 작성하시오.
입력
두 양의 정수 a , b 가 입력으로 주어진다. (1 <= a , b <= 100 000)출력
최대공약수,최소공배수를 한 줄에 출력한다. 두 수의 최대공약수 와 최소 공배수는 정수 범위(2^31 - 1)를 넘지 않는다.입출력 예
입력 8 12 출력 4 24
[문제 풀이]
유클리드 호제법
유클리드 호제법(- 互除法, Euclidean algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
- Wiki, 위키백과 -
1. 입력으로 두 수 m,n(m>n)이 들어온다.
2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
3. n이 m을 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3으로 돌아온다.
최소공배수(lcm) = (A*B) / gcd(A, B);
'알고리즘 > 재귀' 카테고리의 다른 글
| [재귀] 계단 오르기 (0) | 2014.05.15 |
|---|---|
| [재귀] x의 y 거듭제곱 (0) | 2014.05.15 |
| [Doc.] 재귀 (recursion) (0) | 2014.05.15 |
