[Algorithm] 최대공약수, 최소공배수 알고리즘

최대공약수 구하기 - 유클리드 호제

public int gcd(int a, int b){
    int x = Math.max(a, b);
    int y = Math.min(a, b);
    
    if(y==0) return x;
    else return gcd(y, x%y);
}

최소공배수 구하기

public int lcm(int a, int b){
    int gcd = gcd(a, b);
    return a * b / gcd;
}