컴퓨터 사이언스/1고리즘
백준 2609 : 최대공약수와 최소공배수
저세상 개발자
2021. 9. 8. 11:54
https://www.acmicpc.net/problem/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 |