[c++] 백준 2609, 1934 최대공약수와 최소공배수, 최소공배수

백준 단계별로 풀어보기 [정수론 및 집합론] 최대공약수와 최소공배수, 최소공배수

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

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

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

1934번: 최소공배수

 

[풀이]

처음 문제는 num을 증가시켜가며 주어진 두 수 a, b를 num으로 나눈 나머지가 0인 수 중 가장 큰 수를 최대공약수로, num을 a, b로 나눈 나머지가 0인 수 중 가장 작은 수를 최소공배수로 하여 구하였다.

두번째 문제에서는 효율을 높이기 위해 유클리드 호제법을 이용하였다. 유클리드 호제법에 따르면 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 다음을 반복하여 나머지가 0이 되었을 때 나누는 수가 두 수의 최대공약수이다. 재귀를 이용하여 유클리드 호제법을 구현, 최대공약수를 구한 후 두 수의 곱을 최대공약수로 나누면 최소공배수를 구할 수 있다.    

 

[코드]

-최대공약수와 최소공배수

#include<iostream>
#include<algorithm>
#include<string>

int main() {
	//최대공약수와 최소 공배수 출력. 24 18 -> 6 72
	int a, b;
	std::cin >> a >> b;
	int max = 0, min, num = 1;
	while (true) {
		if (a % num == 0 && b % num == 0 && max < num) {
			max = num;
		}
		if (num % a == 0 && num % b == 0) {
			min = num;
			break;
		}
		num++;
	}

	std::cout << max << "\n" << min;

}

-최소공배수

#include<iostream>
#include<algorithm>
#include<string>

int rgcd(int x, int y) {
	if (x % y == 0)
		return y;
	else return rgcd(y, x % y);
}

int main() {
	int n;
	int a, b;
	std::cin >> n;
	for (int i = 0; i < n; i++) {
		std::cin >> a >> b;
		int gcd, lcm;
		std::cout << (a * b) / rgcd(a, b) << "\n";
	}


}