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

1. 최대공약수

최대공약수(GCD, Greatest Common Divisor) : 두 수의 공통된 약수 중 가장 큰 약수

'유클리드 호제법(Euclidean algorithm)'을 사용하면 효율적으로 구할 수 있음

 

[x와 y의 최대공약수를 구하는 법]

1) 자연수 x와 y에 대하여 x를 y로 나누어 r을 얻는다. (단, x > y일 때)

2) 다시 y를 r로 나누어 r2를 얻는다.

3) 이를 반복하다가 나머지 rn이 0이 되면 y가 최대공약수가 된다.

public static void main(String[] args) {
    int x = 72;
    int y = 30;
    
    int result = gcd(x, y);
}

public static int gcd(int x, int y) {
    if(y == 0)
        return x;
    else
        return gcd(y, x % y);
}

 

 

2. 최소공배수

최소공배수(LCM, Least Common Multiple) : 두 수의 공통된 배수 중 가장 작은 배수

최소공배수는 두 수를 곱한 값을 최대공약수로 나눈 것과 같음

public static void main(String[] args) {
    int x = 72;
    int y = 30;
    
    int result = x * y / gcd(x, y);
}

public static int gcd(int x, int y) {
    if(y == 0)
        return x;
    else
        return gcd(y, x % y);
}