[C++/백준] 1934 최소공배수

#1934 최소공배수
https://www.acmicpc.net/problem/1934

📝문제 포인트

1. 최대공약수를 구한다 (그냥 / 유클리드 호제법)
2. 최소공배수 = a*b / 최대공약수

   ---

✍코드

최대공약수를 구하는 첫 번째 방법

#include <iostream>
#include <algorithm>
using namespace std;
int maxNum(int a, int b) { //최대공약수 구하는 함수
	int n = min(a, b);
	int result;
	for (int i = 1; i <= n; i++) {
		if (a % i == 0 && b % i == 0)
			result = i;
	}
	return result;
}
int main() {
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		int a, b, max;
		scanf("%d %d", &a, &b);
		max = maxNum(a, b); //최대공약수
		cout << a * b / max<<'\n';
	}
}

최대공약수를 구하는 두 번째 방법(추천, 유클리드 호제법)

#include <iostream>
#include <algorithm>
using namespace std;
int GCD(int a, int b){
	if (b == 0) return a;
	else return GCD(b, a % b);
}
int main() {
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num; i++) {
		int a, b, maxNum;
		scanf("%d %d", &a, &b);
		maxNum = GCD(a, b); //최대공약수
		cout << a * b / maxNum<<'\n';
	}
}

📝유클리드 호제법?

->2개의 자연수의 최대공약수를 구하는 알고리즘

비교대상의 두 개의 자연수 a와 b에서(단 a>b) a를 b로 나눈 나머지를 r이라고 했을때 GCD(a, b) = GCD(b, r)과 같고 "r이 0이면 그때 b가 최대공약수이다."라는 원리를 활용한 알고리즘입니다.

ex) GCD(24,16) -> GCD(16,8) -> GCD(8,0) : 최대공약수 = 8

참고 : https://coding-factory.tistory.com/599