[백준/c++] 2609번: 최대공약수와 최소공배수

 

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

최대 공약수 - 공통된 약수 중 가장 큰 수

int gcd(int a, int b){ //a>b
    if(b == 0) return a;
    return gcd(b, a%b);
}

 

최소 공배수 - 공통된 배수 중 가장 작은 수

최소공배수 = 두 자연수의 곱 / 최대공약수

 

 

#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int a, int b){
    if(b==0) return a;
    return gcd(b, a%b);
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    if(n < m) swap(n, m);
    int ans = gcd(n, m);
    cout << ans << '\n';
    cout << n * m / ans << '\n';
    return 0;
}