[C++] BOJ (백준) 2609 : 최대공약수와 최소공배수

문제

2609번: 최대공약수와 최소공배수 (acmicpc.net)

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

코드

#include <iostream>

using namespace std;

int gcd(int x, int y) {
  for (int i = min(x, y);; i--) {
    if (x % i == 0 && y % i == 0) return i;
  }
}

int lcm(int x, int y) {
  for (int i = max(x, y);; i++) {
    if (i % x == 0 && i % y == 0) return i;
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int x, y;
  cin >> x >> y;

  cout << gcd(x, y) << '\n' << lcm(x, y);
}

 

설명

브루트포스로 최대공약수는 1씩 감소, 최소공배수는 1씩 증가시켜가며 구한다.
문제 의도는 이게 아닌 것 같긴 한데 어쨌든 제한 시간 내에 풀린다.

 

코드2

#include <iostream>

using namespace std;

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

int lcm(int x, int y) {
  return x * y / gcd(x, y);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int x, y;
  cin >> x >> y;

  cout << gcd(x, y) << '\n' << lcm(x, y);
}

 

설명

유클리드 호제법으로 최대공약수를 구한다.
최소공배수는 '두 수의 곱 / 최대공약수'로 구할 수 있다.

코드1은 거의 200ms가 걸렸는데 코드2는 0ms로 통과하였다.