백준 2609 : 최대공약수와 최소공배수

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

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

 

gcd는 유클리드 알고리즘으로 구하고, lcm은 수학적으로 a * b / gcd(a,b) 로 구할 수 있다.

아래 코드에서는 그냥 lcm도 따로 구현했다.

 

#include <iostream>

using namespace std;

int gcd(int a, int b) {
	int n;
	if (a < b) {
		int tmp = a;
		a = b, b = tmp;
	}
	while (b != 0) {
		n = a % b;
		a = b, b = n;
	}

	return a;
}

int lcm(int a, int b) {
	int cura = a, curb = b;
	while (cura != curb) {
		if (cura < curb) cura += a;
		else curb += b;
	}

	return cura;
}

void solution() {
	int a, b;
	cin >> a >> b;

	cout << gcd(a, b) << '\n';
	cout << lcm(a, b);
}

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

	return 0;
}

메모리: 2020 kb

시간: 0 ms