유클리드 호제법

손으로하면 참 쉬운 최대공약수 (GCD), 최소공배수(LCM)가 코드로 짜면 좀 쉽지가 않다.
그래서 우리가 쓰는게 유클리드 호제법이다.

원리는 인터넷 찾아보고

n m 이 있을 때, m == 0이면 gcd는 n
그렇지 않으면 gcd(m, n % m) 반환

#include <iostream>
using namespace std;

int n, m, gcdn, lcm;
int gcd(int n, int m);

int main() {
    cin >> n >> m;
    gcdn = gcd(n, m);
    lcm = n * m / gcdn;
    cout << gcdn << "\n";
    cout << lcm;
}

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