최대공약수와 최소공배수

작성일 | In

[백준] 2609번 - 최대공약수와 최소공배수

문제 링크

최대공약수와 최소공배수의 성질을 알면 쉽게 풀 수 있다.
최대공약수의 경우 1부터 두 수 중 작은 수까지 탐색하며 해당 수가 주어진 두 수를 모두 나머지 0으로 나눌 수 있는지를 살펴보면 된다.
최소공배수는 구하는 공식이 존재한다. 두 수가 a,b이고, 최대공약수를 L이라 할 때, 최소공배수 G는 a * b / L이다.

최소공배수 구하는 공식이 어떻게 성립하는지 살펴보자. 두 수가 48과 60일 때, 48 = 24 x 3 이고, 60 = 22 x 3 x 5 이다.
최대공약수를 구하는 방법은 아래와 같다.

  1. 두 수의 공통된 소인수를 찾는다.
  2. 소인수의 지수가 낮은 수를 선택한다.
  3. 선택된 수를 전부 곱한다.

48과 60의 공통된 소인수는 2와 3이고, 지수가 낮은 소인수를 선택하면 22과 3이 선택된다.
이 두 수를 곱하면 12가 최대공약수임을 알 수 있다.

최소공배수는 아래와 같은 방법으로 찾을 수 있다.

  1. 기본적으로 두 수의 소인수를 전부 곱한다.
  2. 만약 공통된 소인수가 있다면, 지수가 높은 수를 선택한다.

48과 60의 소인수에는 2,3,5가 존재하고, 2와 3은 공통된 소인수이다. 지수가 높은 수를 선택하면 24과 3이 선택된다. 즉, 24 x 3 x 5 = 240이 최소공배수이다.

최대공약수와 최소공배수 구하는 방법을 살펴봤으니 감이 올 것이다. 두 수를 곱하는 과정에서 두 수의 소인수들이 합쳐지게된다.
최소공배수를 구할 땐 공통된 소인수의 경우 지수가 높은 것을 선택했지만, 두 수를 곱할 땐 공통된 소인수의 지수가 서로 더해진다.
두 수의 곱에서 공통된 소인수들 중 지수가 낮은 수가 곱셈되는 연산을 없애야하고, 공통된 소인수들 중 지수가 낮은 수들만 모아 곱한 수가 최대공약수이므로 두 수의 곱에서 최대공약수를 나누면 최소공배수를 구할 수 있는 것이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main(void) {
    int a,b;
    scanf("%d %d", &a, &b);

    if(a > b) {
        a ^= b; b^= a; a ^= b;
    }

    int gcf, lcm;
    for(int i=1; i<=a; ++i) {
        if(a % i == 0 && b % i == 0)
            gcf = i;
    }

    lcm = a * b / gcf;

    printf("%d\n%d", gcf, lcm);
}
0%