유클리드 호제법을 이용한 최소공배수, 최대공약수

최대공약수

// 방법 1
public int getGCD(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    
    return a;
}


// 방법 2
public int getGCD(int a, int b) {
    if (b == 0) 
        return a;
     
    return getGCD(b, a % b);
}

 

 

최소공배수

public int getLCM(int a, int b) {
    return (a * b) / getGCD(a, b);
}