[BOJ] 2609번: 최대공약수와 최소공배수 (C, C++, Java, Python3)

 

2609번: 최대공약수와 최소공배수

 

 

문제

---

 

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

 

입력

---

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

 

출력

---

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

 

 

힌트

---

아직 유클리드 호제법을 잘 모른다면 아래 링크를 통해 유클리드 호제법을 먼저 보고 오자.

 

[알고리즘 기초] 유클리드 호제법, GCD(최대공약수) 구하기

 

입력 범위가 1만 이하의 자연수로 크지 않아서 단순 반복문으로 약수에 해당하는 범위를 탐색해도 충분히 해결할 수 있다.

 

풀이

---

주어진 두 자연수를 A, B라고 했을 때, A와 B 중 더 작은 수부터 시작하여 1까지 반복하면서 두 수를 나누어보면 최대공약수를 찾아낼 수 있다. 최소 공배수는 A와 B를 각각 최대공약수로 나눠준 후 두 수를 곱하고 거기에 다시 최대공약수를 곱해주면 된다.

 

애초에 GCD를 구할 때 반복문으로 모든 수를 탐색해가면서 해답을 구하는 건 좋은 방법이 아니므로 여기서는 유클리드 호제법을 사용한 풀이만 제공하고자 한다

 

 

 

C

#include <stdio.h>

int get_gcd(int A, int B)
{
    if(B == 0) return A;
    else return get_gcd(B, A % B);
}

int main(){
    int A, B, R, gcd, lcm;

    scanf("%d %d", &A, &B);

    gcd = get_gcd(A, B);
    lcm = A * B / gcd;

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

 

C++

#include <iostream>
using namespace std;

int get_gcd(int A, int B)
{
    int R = A % B;

    if(R == 0) return B;
    else return get_gcd(B, R);
}

int main(){
    int A, B, gcd, tmp;

    cin >> A >> B;

    gcd = get_gcd(A, B);

    cout << gcd << "\n";
    cout << (A / gcd) * (B / gcd) * gcd;

    return 0;
}

 

Java

import java.util.Scanner;

public class Main {
    public static int get_gcd(int A, int B)
    {
        if(B == 0) return A;
        else return get_gcd(B, A % B);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt(), B = sc.nextInt();
        int gcd = get_gcd(A, B);
        int lcm = A * B / gcd;

        System.out.println(gcd);
        System.out.println(lcm);
        sc.close();
    }
}

 

 Python3

def get_gcd(A, B):
    if not B:
        return A
    
    else:
        return get_gcd(B, A % B)

A, B = map(int, input().split())
gcd = get_gcd(A, B)
lcm = A * B // gcd

print(gcd)
print(lcm)