[JAVA-알고리즘] 5. 최소공배수

package algo;
// 공식 LCM = a*b/GCD(a%b=b, a%b)
// 18(a)와 12(b)의 최소공배수 (18와 12의 최대공약수는 6)
// 18(a) * 12(b) / 6

// gcd
// 18(a) % 12(b) = 6(c)
// 12(a) % 6(b) = 0(c)
// 6(a) % 0(b) = 0(c)

// lcm
// 18(a) * 12(b) / gcd (b=6)

public class Lcm01 {
    static int gcd(int a, int b) {
        while (true) {
            int c = a % b;
            a = b;
            b = c;
            if (c == 0) {
                break;
            }
        }
        return a;
    }

    public static void main(String[] args) {

        int a = 18;
        int b = 12;

        System.out.println("두 수의 최대공약수는 : " + gcd(a, b));

        int c = a * b / gcd(a, b);
        System.out.println("두 수의 최소공배수는 : " + c);
    }
}