백준 2609번: 최대공약수와 최소공배수(유클리디안 호제법)

 

그냥 유클리디안 호제법을 마음으로 받아들이자.

 

#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a, int b) {
	while (b != 0) {
		int r = a % b;
		a = b;
		b = r;
	}
	return a;
}

int lcm(int a, int b, int c) {
	return a * b / c;
}
	
int main() {
	int M, N;
	cin >> M >> N;
	int c = gcd(M, N);
	cout << c << '\n' <<lcm(M, N, c);

	return 0;
}