백준_1934_최소공배수

최소공배수를 구하는 문제입니다.

 

중학교 때 배웠던 소인수분해를 기억하시나요?

 

만약 8과 16이라는 두 수가 주어졌을 때, 소인수분해를 통해 최대공약수와 최소공배수를 구할 수 있습니다.

아래의 표는 소인수분해의 과정을 나타낸 것입니다.

2	8	16
2	4	8
2	2	4
	1	2

 

여기서 좌측의 노란색 배경 숫자들을 곱하면 최대공약수, 

최대공약수에 초록 배경 숫자들까지 곱해주면 최소공배수를 구할 수 있습니다.

 

8과 16의 최대공약수는 2*2*2 = 8 이 되겠고,

최소공배수는 2*2*2*1*2 = 16 이 되겠죠.

 

소인수분해의 과정만 코드로 구현한다면, 이 문제를 해결할 수 있습니다.

 

 

최대공약수,최소공배수 구하는 함수)

int common(int a, int b)
{
    int divisor = 1;
    for (int i = 2; a >= i && b >= i;)
    {
        if (a % i == 0 && b % i == 0)
        {
            a /= i;
            b /= i;
            divisor *= i;
            i = 2;
        }
        else
        {
            i++;
        }
    }
    return divisor * a * b;
}

 

두 숫자 a와 b를 입력받아 소인수분해하는 함수입니다.

 

i가 2부터 1씩 커지며 공통 약수를 찾습니다.

공통 약수라면 a 와 b를 한번씩 나누어주고 다시 2부터 약수를 찾는 과정을 반복합니다.

 

언제까지? a와 b가 i 보다 작아질 때까지 반복합니다.

 

그리고 이 과정을 한 번 반복할 때마다 divisor 변수에 약수를 계속 곱해줍니다.

 

모든 과정이 끝나고 나면, divisor 변수에는 최대공약수가 남아있을 것이고, a와 b는 더이상 공통약수가 없는 숫자이겠죠.

 

그래서 divisor * a * b 를 해주면 최대공약수가 나오는 것입니다.

 

 

 

전체 코드)

#include <stdio.h>

int common(int a, int b);

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

    int a, b;
    for (int i = 0; i < T; i++)
    {
        scanf("%d %d", &a, &b);

        if (a == b)
        {
            printf("%d\n", a);
        }
        else
        {
            printf("%d\n", common(a, b));
        }
    }
    return 0;
}

int common(int a, int b)
{
    int divisor = 1;
    for (int i = 2; a >= i && b >= i;)
    {
        if (a % i == 0 && b % i == 0)
        {
            a /= i;
            b /= i;
            divisor *= i;
            i = 2;
        }
        else
        {
            i++;
        }
    }
    return divisor * a * b;
}

 

a와 b가 같다면 소인수분해를 할 필요가 없으니 바로 출력하도록 하는 조건도 추가해주었습니다.!