[BOJ] 백준 #13241. 최소공배수 (C++)

🎨 문제

문제 링크: https://www.acmicpc.net/problem/13241

• 알고리즘 분류: 유클리드 호제법, 수학
• 난이도: Silver Ⅲ

💬 풀이

백준 #1850에서 유클리드 호제법을 이용해 최대공약수(gcd)를 구했었다.
유클리드 호제법을 다시 간단히 떠올려보면, gcd(A,B) = gcd(B,r)

✔ 최소공배수 구하기

최소공배수(lcm)는 바로 이 최대공약수를 이용해서 구할 수 있다. lcm × gcd = A × B

👩‍💻 코드

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;

long long GCD(long long a, long long b) {
	if (a % b == 0) { return b; }
	else { return GCD(b, a % b); }
}

long long LCM(long long a, long long b) {
	return a * b / GCD(a, b);
}

int main() {
	//freopen("input.txt", "rt", stdin);
	long long A, B;
	cin >> A >> B;
	
	long long lcm = LCM(A, B);
	cout << lcm;

	return 0;
}