[백준 2609] 최대공약수와 최대공배수 (Java)

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

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

접근 방법

최대 공약수의 경우 유클리드 호제법을 적용하였다.

a와 b의 최대 공약수를 구할 때,

a와 b 나눠 나머지가 생기면

b와 그 나머지를 다시 나누고 그렇게 생긴 나머지를

처음 나머지와 그 다음 나머지를 다시 나누고....

나머지가 없을 때까지 나누는데 이 때 나머지가 없을 때의 나눈 값이 최대공약수가 된다.

(자세한 내용은 여기)

 

최소 공배수는 a와 b를 최대공약수로 나누고 그 값들을 곱한 값이 된다.

즉, 최소 공배수 = 최대 공약수 * (a / 최대 공약수) * (b / 최대 공약수)

 

 

최종 코드

import java.util.Scanner;

public class Main {

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

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

        int gcd = euclid(a, b);
        int lcm = lcm(a, b);

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

    private static int lcm(int a, int b) {
        int gcd = euclid(a, b);
        int total = gcd * (a / gcd) * (b / gcd);

        return total;
    }

    private static int euclid(int a, int b) {
        int num = b;

        while (num != 0) {
            if (a % num != 0) {
                int temp = a;
                a = num;
                num = temp % num;
            } else {
                break;
            }
        }

        return num;
    }
}