백준 5347번 : LCM(C 언어)

https://www.acmicpc.net/problem/5347

5347번: LCM

Code:

#include <stdio.h>
 
long long gcd(long long a, long long b)
{
    long long A, B;
    if (a > b)
    {
        A = a;
        B = b;
    }
    else
    {
        A = b;
        B = a;
    }
    if (B == 0)
    {
        return A;
    }
    return gcd(B, A % B);
}
 
long long lcm(long long a, long long b)
{
    return (a * b) / gcd(a, b);
}
 
int main() {
    long long a, b;
    long long n;
    scanf("%lld", &n);
    while (n--)
    {
        scanf("%lld %lld", &a, &b);
        printf("%lld\n", lcm(a, b));
    }
    return 0;
}

문제 설명:

두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성해야 합니다.

입력: 첫째 줄에는 테스트 케이스의 개수 n이 주어집니다. 다음 n개 줄에는 a와 b가 주어집니다. a와 b 사이에는 공백이 하나 이상 있습니다. 두 수는 백만보다 작거나 같은 자연수입니다.

출력: 각 테스트 케이스에 대해 입력으로 주어진 두 수의 최소 공배수를 출력합니다.

코드 설명:

 

그리고 n번 반복하면서 a와 b를 입력받고, lcm 함수를 사용하여 a와 b의 최소 공배수를 계산하고 출력합니다.

최소 공배수를 구하는 과정에서 gcd 함수를 사용합니다. gcd 함수는 두 수의 최대 공약수를 계산하는 함수입니다. gcd 함수는 재귀적으로 구현되어 있으며, 유클리드 호제법을 사용하여 최대 공약수를 구합니다.

lcm 함수는 주어진 두 수 a와 b의 곱을 최대 공약수로 나눈 값을 반환합니다. 이를 통해 최소 공배수를 구할 수 있습니다.

이렇게 작성된 코드는 입력으로 주어진 테스트 케이스에 대해 각각의 a와 b에 대한 최소 공배수를 계산하고 출력합니다.