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

www.acmicpc.net/problem/2609

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

유클리드 알고리즘을 이용하여 최대 공약수를 구하고, 최대 공약수를 활용해서 최소 공배수를 구한다.

 

코드

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

//유클리드 알고리즘을 이용하여 최대 공약수를 구한다
int gcd(int p, int q)
{
	if (q == 0)
		return p;

	return gcd(q, p % q);
}

//최소 공배수를 반환한다
int lcm(int p, int q)
{
	//p,q의 최대 공약수를 구한다
	int this_gcd = gcd(p, q);

	return this_gcd * (p / this_gcd) * (q / this_gcd);
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int input1, input2;

	cin >> input1 >> input2;

	cout << gcd(input1, input2) << "\n";
	cout << lcm(input1, input2);

	return 0;
}