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

 📚 문제

[BOJ C++] 백준 2609번: 최대공약수와 최소공배수
https://www.acmicpc.net/problem/2609

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 최대공약수, 최소공배수를 구할 때는 유클리드 호제법을 사용한다. (아래 글 참고)
• 유클리드 호제법

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;
int gcd(int n, int m);

int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(0);
    int n, m, g, l;
    cin >> n >> m;
    g = gcd(n, m); // 최대공약수.
    n /= g;
    m /= g;
    l = n * m * g;
    cout << g << '\n' << l;
}

int gcd(int n, int m) { // 유클리드 호제법.
    if (n < m)
        swap(n, m);

    if (m == 0)
        return n;
    else
        return gcd(m, n % m);
}