/ 알고리즘

유클리드호제법

알고리즘 유클리드 호제법
https://4am.kr/-ec-9c-a0-ed-81-b4-eb-a6-ac-eb-93-9c-ed-98-b8-ec-a0-9c-eb-b2-95/

프로그램 명: euclid

제한시간: 1 초

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

입력
두 양의 정수 a , b 가 입력으로 주어진다. (1 <= a , b <= 100 000)
출력
최대공약수,최소공배수를 한 줄에 출력한다. 두 수의 최대공약수 와 최소 공배수는 정수 범위(2^31 – 1)를 넘지 않는다.
입출력 예
입력

8 12

출력

4 24

출처:
채점 데이터:

#include <iostream>
using namespace std;
//최대공약수 GCD
/* 
1. 입력으로 두 수 a,b(a>b)가 들어온다.
2. b가 0이라면 a를 출력하고 알고리즘을 종료한다. 
3. b가 a를 나누어 떨어지면, b를 출력하고 알고리즘을 종료한다. 
4. 그렇지 않으면 a를 b로 나눈 나머지를 새롭게 a에 대입하고 a와 b를 바꾸고 앞 과정으로 돌아온다. 
*/
int gcd(int a, int b)
{
    if (a % b == 0)
        return b;
    else
        return gcd(b, a % b);
    //다른 구현 방법 return b ? gcd(b, b%a) : a;
}
//최소공배수 LCM
/* LCM = (A*B) / GCD(A,B) */
int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

int main()
{
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << " " << lcm(a, b) << endl;
    return 0;
}