[JAVA-자바] 2609번: 최대공약수와 최소공배수

 

두 개의 자연수를 입력받은 뒤, 최대 공약수와 최소 공배수를 출력하는 문제입니다.

---

최대공약수 (greatest common divisor, gcd) :
두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수는 이름 그대로 공약수 중 가장 큰 것을 가리킨다.

 

24의 약수는 (1, 2, 3, 4, 6, 8, 12, 24)

18의 약수는 (1, 2, 3, 6, 9, 18)

겹치는 약수는 (1, 2, 3, 6)이며, 이 중 최대공약수는 6입니다.

---

최소공배수 (least common multiple, lcm) :
두 수, 혹은 그 이상의 수들의 공통인 배수라는 뜻이다. 최소공배수(least common multiple)는 당연히 공배수 중에서 가장 작은 것을 가리킨다.

 

24의 배수는 (24, 48, 72, 96, ...)

18의 배수는 (18, 36, 54, 72, ...)

겹치는 배수들 중, 최소공배수는 72입니다.

---

최대공약수를 구하는 방법은 여러가지가 있지만, 가장 단순하게 생각해서 접근해보겠습니다.

 

방법은, 두 수의 공약수를 전부 구하고, 그중 가장 큰 공약수를 선택하는 방법입니다.

 

알고리즘:

1. 두 수(a, b) 중 작은 수(n)을 구한다.

2. 1부터 n까지 반복하며 두 수를 나머지 없이 나눌수 있는 가장 큰 숫자를 찾는다.

 

최대공약수를 구하는 함수:

public static int getGCD(int a, int b) {
    int GCD = 1;
    for (int i = 1; i <= Math.min(a, b); i++) {
        if ((a % i == 0) && (b % i == 0)) {
            GCD = i;
        }
    }
    return GCD;
}

---

마찬가지로 최소공배수도 구하는 방법이 여러가지가 있지만, 가장 단순한 방법을 사용하겠습니다.

 

방법은, 두 수중 가장 큰 수를 구한 뒤 1씩 증가시키면서 각각 a와 b로 나누어 떨어지는 수를 구하는 방법입니다.

 

알고리즘:

1. 두 수(a, b)의 큰 값(n)을 구한다.

2. n부터 a * b 까지 1씩 증가하며 a와 b로 나누어 떨어지는 수를 찾는다.

 

최소공배수를 구하는 함수:

public static int gebLCM(int a, int b) {
    for (int i = Math.max(a, b); i <= a * b; i++) {
        if ((i % a == 0) && (i % b == 0)) {
            return i;
        }
    }
    return a * b;
}

---

메인 함수:

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int a = sc.nextInt();
    int b = sc.nextInt();

    sc.close();

    System.out.println(getGCD(a, b));
    System.out.println(gebLCM(a, b));
}

 

출력 결과

---

 

 

본 문서에서는 유클리드 호제법을 일부러 사용하지 않았습니다.

추후에 다른 문제에서 다루게 된다면 자세하게 작성하도록 하겠습니다!

 

글의 내용 중 잘못된 점이나 수정이 필요한 부분, 혹은 궁금한 사항이 있다면 언제든 댓글로 남겨주시면 감사하겠습니다.

여러분의 피드백은 더 나은 글을 작성하는 데 큰 도움이 됩니다. 감사합니다.