[BOJ/백준] C++ 2609번 최대공약수와 최소공배수 문제풀이

⭐️ 문제

⭐️ 코드

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

int gcd(int a, int b) {
	int maxdiv = 0;
	int range = min(a, b);

	for (int i{ 1 }; i <= range; i++) {
		if (a % i == 0 && b % i == 0) {
			maxdiv = i;
		}
	}
	return maxdiv;
}

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

	int num1, num2 = 0;
	cin >> num1 >> num2;

	cout << gcd(num1, num2) << "\n";
	cout << (num1 / gcd(num1, num2)) * (num2 / gcd(num1, num2)) * gcd(num1, num2);

	return 0;
}

🔻 다른 풀이 #1

#include <iostream>
using namespace std;

// 최대공약수 구하기
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}

// 최소공배수 구하기
int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}

int main() {
	int n1, n2;
	cin >> n1 >> n2;
	cout << gcd(n1, n2) << "\n" << lcm(n1, n2);
}

✔️ 최소공배수 구하는 함수 코드

int lcm(int a, int b) {
	return (a * b) / gcd(a, b);
}

최대공약수*최소공배수 = 두 수의 곱

출처 : https://sectumsempra.tistory.com/77