JAVA) 2609번 최대공약수와 최소공배수 구하기

최대공약수를 구하기 위해 유클리드 호제법을 사용했고

최소공배수를 사용하기 위해 구한 최소공배수 값을 활용했다.

cf) 유클리드 호제법 :

   GCD(a, b) = GCD(b, r)이다.

   이 때, r = a를 b로 나눈 나머지이다.
   r = 0이 될때, b가 최대공약수가 된다.
   ex) GCD(24, 16) = GCD(16, 8) = GCD(8, 0) -> 최대공약수 = 8

cf) 최소공배수 = gcd*(a/gcd)*(b/gcd)이다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        int GCD = gcd(num1, num2);
        System.out.println(GCD);
        System.out.println(lcm(GCD, num1, num2));

    }

    public static int gcd(int a, int b) { // 유클리드 호제법 사용
        while (b != 0) {
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }

    public static int lcm(int gcd, int a, int b) {
        return gcd*(a/gcd)*(b/gcd); // 최소공배수 LCM = gcd*(a/gcd)*(b/gcd)이다.
    }
}