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

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

---

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

[Python] 코드

def GCD(num1, num2):
    while num2 != 0:
        num1, num2 = num2, num1 % num2
    return num1

def LCM(num1, num2):
    return (num1*num2) / GCD(num1, num2)

A, B = map(int, input().split())
if A < B:
    A, B = B, A

print(GCD(A, B), int(LCM(A, B)))

 

풀이

1. GCD : 최대공약수 구하는 함수. 유클리드 호제법 알고리즘을 사용했다.

2. LCM : 최소공배수를 구하는 함수. 두 수의 곱에 최대공약수를 나눠주면 나온다.

3. 유클리드 호제법을 사용할 때, 큰 수가 앞에 있어야 하므로 A, B를 받았을 때 A가 B보다 작다면 그 순서를 바꿔준다.

4. 그리고 연산을 끝낸 결과를 출력한다.

 

[C] 코드

#include <stdio.h>

int GCD(int num1, int num2)
{
    while (num2 != 0)
    {
        int temp = num2;
        num2 = num1 % num2;
        num1 = temp;
    }
    return num1;
}

int LCM(int num1, int num2)
{
    return (num1 * num2) / GCD(num1, num2);
}

int main(void)
{
    int num1, num2;

    scanf("%d %d", &num1, &num2);
    
    if (num1 < num2)
    {
        int temp = num1;
        num1 = num2;
        num2 = temp;
    }

    int gcd = GCD(num1, num2);
    int lcm = LCM(num1, num2);
    printf("%d %d", gcd, lcm);

    return 0;
}

 

풀이

파이썬 코드 로직과 일치한다.