[BOJ/C++] 2609. 최대공약수와 최소공배수

https://www.acmicpc.net/problem/2609

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

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

해결 방법

바로 떠오른 것은 유클리드 호제법이라는 알고리즘이었다. 사전에 지식이 있었기 때문이다.

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

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

int gcd(int a, int b)
{
    int c;
	while(b)
	{
		c = a % b;
		a = b;
		b = c;
	}
    return a;
}

위키디피아에서 소스코드를 보면 다음과 같이 흘러간다.

이것을 재귀법으로 구현하고 LCM인 최소공배수는 두수의 곱에 최대공약수를 나누면 해결이 된다.

// Code Plus BasicA
// 0x00. Math
// Written by Rylah
// Written Date : 2022.01.13
// https://minteul.tistory.com/307
// https://www.acmicpc.net/source/37502374

// 2609. 최대공약수와 최소공배수
// use Euclidean Algorithm
// time Complexity : O(logN)


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

int gcd(int a, int b)
{
	if (b == 0) // GCD Find State
		return a;
	else // Recursive Find GCD
		return gcd(b, a % b);
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int a, b;
	cin >> a >> b;
	int gcdValue = gcd(a, b);
	cout << gcdValue << "\n";
	// LCM is A * B / GCD(A, B)
	cout << a * b / gcdValue << "\n";
	return 0;
}