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

문제

입출력

풀이

유클리드 호제법으로 문제를 풀 수 있다.

유클리드 호제법은 두개의 자연수 a, b에서 a를 b로 나눈 나머지 r이라 했을때
GCD(a,b) = GCD(b,r)이고 r이 0이면 그때 b가 최대 공약수라는 원리를 이용한 알고리즘이다.
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95

코드

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
	while (true)
	{
		int r = a % b;
		if (r == 0)
			break;
		else
		{
			a = b; 
			b = r; 
		}
	}
	return b;
}
int lcm(int a, int b)
{
	return a * b / gcd(a, b);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;

	if (m > n)
		swap(n, m);
	cout << gcd(n, m) << '\n' << lcm(n, m);
}