[자바 알고리즘] 41. 최소공배수

package algo;

public class Util {
    // 두 정수 A와 B를 인자로 받아 최대 공약수를 재귀적으로 계산합니다.
    // B가 0일 경우 A가 최대 공약수입니다.
    // 그 외의 경우에는 GCD(B, A % B)를 호출하여 최대 공약수를 계속 계산합니다.
    
    static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }
}

4의 배수 : 4,8,12,16,20,24,28,32,36
9의 배수 : 9,18,27,36

최소 공배수는 36

import java.util.Scanner;

public class LCM01 {
    public static void main(String[] args) {
        // LCM = a*b/GCD
        // 4와 9의 최소공배수를 구하여라

        // 4의 공배수 4, 8, 12, 16, 20, 24, 28, 32, 36
        // 9의 공배수 9, 18, 27, 36, 45, 54, 63, 72

        Scanner sc = new Scanner(System.in);
        System.out.println("두 정수를 입력하시오 : ");
        int a = sc.nextInt();
        int b = sc.nextInt();

        // 최소공배수를 구하는 공식
        int lcm;
        lcm = a * b / Util.gcd(a, b);
        System.out.println(a + "와" + b + "의 최소공배수는 " + lcm);
    }
}