[Baekjoon/JAVA] 2609번 - 최대공약수와 최소공배수

Baekjoon Online Judge

문제로 이동

 

문제

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

 

입력

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

 

출력

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

 

---

예제 입력	예제 출력
24 18	6 72

---

풀이

import java.util.Scanner;

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

        int num1 = in.nextInt();
        int num2 = in.nextInt();

        int i = 2;
        int multi = 1;

        // 최대공약수 구하기
        while(true) {
            if (num1 < i || num2 < i) break;

            if (num1 % i == 0 && num2 % i == 0) {
                num1 /= i;
                num2 /= i;
                multi *= i;
            }
            else i++;
        }

        // 출력
        System.out.println(multi);
        System.out.println(multi * num1 * num2);
    }
}

두 개의 자연수의 최대 공약수와 최소 공배수를 구하는 방법은 아래와 같다.

 

두 수의 공약수로 더이상 나눌 수 없을 때까지 두 수를 나눈다. 그리고 이 때 사용한 숫자와 최종적으로 나누고 남은 숫자를 이용한다.

- 최대 공약수 : 2 * 3 = 6

- 최소 공배수 : 2 * 3 * 4 * 3 = 72

 

 

        int i = 2;
        int multi = 1;

        // 최대공약수 구하기
        while(true) {
            if (num1 < i || num2 < i) break;

            if (num1 % i == 0 && num2 % i == 0) {
                num1 /= i;
                num2 /= i;
                multi *= i;
            }
            else i++;
        }

위 공식을 그대로 코드로 구현했다. i로 두 수가 모두 나누어떨어지면 두 수를 i로 나누고 i를 multi에 곱했다. 나누어 떨어지지 않다면 i를 1씩 증가시켰다. 이를 반복하다 i가 두 수보다 크면 반복문을 종료시켰다.

 

        System.out.println(multi);
        System.out.println(multi * num1 * num2);

multi는 최대공약수를 구한 것이므로 그냥 출력하고, 최소공배수는 multi에 나누고 남은 숫자 2개를 곱해서 출력했다.