[백준2609번] 최대공약수와 최소공배수

문제

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

입력

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

출력

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

예제 입력 1

24 18

예제 출력 1

6
72

나의 풀이

이 문제는 최대공약수를 먼저 구하고 최대공약수를 이용하여 최소공배수를 구하면 쉽게 풀 수 있다. 최대공약수를 구하는 알고리즘으로는 유클리드 호제법이 있다. 간단히 설명하면 x, y (x > y) 두 개의 수가 있다면 y로 x가 나누어 떨어질때까지 반복으로 구하는 것인데 만약 여기서 나누어 떨어지지 않는다면 x에는 y를 y에는 y로 x로 나누었을때의 나머지를 저장하면 된다. 24와 18이 각각 x,y로 주어졌을때를 보여주자면 (24,18) => (18,6) => (6,0) 와 같이 구해지며 y가 0이 되었을 때의 x값이 최대공약수가 된다.

그럼 이렇게 최대공약수를 구하면 최소공배수를 구하면 되는데 최소공배수는 처음 입력받은 x, y를 각각 최대공약수로 나눈 수들을 곱하고 최대공약수를 곱해주면 된다. 이를 수식으로 나타내면 x/최대공약수 * y/최대공약수 * 최대공약수 => (x * y) / 최대공약수가 된다.

코드

import java.util.Scanner;

/**
 * 2609번 최대공약수와 최소공배수
 */
public class Baeckjun2609 {
    static int gcf, lcm, x, y;

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

        // x가 y보다 커야 최대공약수를 구할 수 있다.
        if (a>b) {
            x = a;
            y = b;
        } else {
            x = b;
            y = a;
        }

        // 최대공약수
        findGcf();

        // 최소공배수
        // 여기서 x,y가 아닌 a,b를 이용하는 이유는 최대공약수를 구할때 x,y값이 바뀌기때문
        lcm = (a * b) / gcf;

        System.out.println(gcf);
        System.out.println(lcm);
    }

    private static void findGcf() {
        while (y!=0) {
            int tmp = x;
            x = y;
            y = tmp % y;
        }
        gcf = x;
    }
}