180528_2609_최대공약수와 최소공배수

	//https://www.acmicpc.net/problem/2609 #include <iostream>
	using namespace std;
	int gcd(int a, int b){
	return b? gcd(b, a%b) : a;
	}
	int main(){
	int a, b;
	cin >> a >> b;
	if(a<b) {
	int tmp=a;
	a=b;
	b=tmp;
	}
	int ans=gcd(a,b);
	cout << ans <<endl;
	cout << a*b/ans <<endl;
	return 0;
	}

>>유클리드 호제법 

 두 자연수 a,b에 대하여 (a>=b) a를 b로 나눈 나머지 r에 대하여, a와 b의 최대공약수와 b와 r의 최대공약수는 서로 같다.

a=AX

b=BX

일때(A와 B는 서로소고, 따라서 X는 최대공약수), a*b=A*B*X*X이므로 

a*b/X=A*B*X 로 최소공배수이다.