백준(S4) 1934번 최소공배수 (C11,C99)

코드를 보기 전에: 최소공배수 구하는 방법! -> A X B / A,B의 최대공약수 = A,B의 최소공배수

 

최대 공약수를 구하는 공식이다.

int Max(int a, int b) 
{
    int result1 = 0;
    int min = (a < b) ? a : b;
    for (int c = 1; c <= min; c++)
    {
        if ((a%c == 0) && (b%c == 0))
        {
            result1 = c;
            if (result1 < c)
                result1 = c;
        }
    }
    return result1;
}

최대공약수는 인수보다 작기때문에 a와 b중에서 더 작은 인수를 구한다.

그다음 반복문을 통해 변수가 0부터 (a와 b중 더 작은 인수)사이에서 반복하게 한다.

a와 b로 나눴을때 0이 되는 변수를 찾는다.

 

 

최소공배수를 구하는 코드다.

a와 b 곱한 뒤 최대공약수로 나눠주면 된다.

int Min(int a, int b) 
{
    return a * b / Max(a, b); 
}

 

 

Fullcode

#include<stdio.h>
int Max(int a, int b) 
{
    int result1 = 0;
    int min = (a < b) ? a : b;
    for (int c = 1; c <= min; c++)
    {
        if ((a%c == 0) && (b%c == 0))
        {
            result1 = c;
            if (result1 < c)
                result1 = c;
        }
    }
    return result1;
}
 
int Min(int a, int b) 
{
    return a * b / Max(a, b); 
}
 
int main(void)
{
    int num, a, b;
    scanf("%d", &num);
 
    for (int i = 0; i < num; i++)
    {
        scanf("%d %d", &a, &b);
        printf("%d\n", Min(a, b));
    }
}