[백준] 2609번 최대공약수와 최소공배수

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

예제 입력 1

24 18

예제 출력 1

6

72

 

소스코드

#include <iostream>
using namespace std;

int GCD(int a, int b) {	//두 수의 최대공약수를 계산하는 함수이다.
    int min;
    
    if(a<b) min=a;	//두 수 중 더 작은 값을 min에 저장한다.
    else min=b;
    
    for(int i=min;i>0;i--) {	//min값부터 시작해서 1씩 줄여가며 두 수를 모두 나누어떨어지게 하는 수를 찾는다.
        if(a%i==0) {
            if(b%i==0) return i;
        }
    }
    return 0;
}

int LSM(int a, int b) {	//두 수의 최소공배수를 계산하는 함수이다.
    int result=a*b;	//두 수의 곱을 result에 저장한다.
    int c=GCD(a, b);
    
    result/=c;	//두 수의 곱을 최대공약수로 나누면 최소공배수가 된다.
    
    return result;
}

int main() {
    int n,m;
    
    cin>>n>>m;
    cout<<GCD(n, m)<<endl<<LSM(n, m);
    
    return 0;
}