최대공약수 구하기 (feat 최소공배수 구하기)

1. 최대공약수 구하기 (gcd)

 

유클리드 호제법

두 개의 정수가 주어졌을 때, 최대공약수를 구하는 알고리즘

• 두 정수 A, B에 대해서, R이 A / B의 나머지이면 최대공약수(A, B) = 최대공약수(B, R)이 성립한다.
• R이 0이 되었을 때 B는 A와 B의 최대 공약수 이다.

private int gcd(int big, int small) {
    if (small > big) {
        int tmp = small;
        small = big;
        big = tmp;
    }

    if (big % small == 0) {
        return small;
    }

    return gcd(small, big % small);
}

예시) 6, 4의 최대공약수

 

2. 최소공배수 구하기 (lcm)

위 유클리드 호제법으로 구한 최대공약수를 활용

• 두 정수 A, B에 대하여 최소공배수는 (A x B) / 최대공약수

private int lcm(int A, int B) {
    return (A * B) / gcd(A, B);
}

예시) 6, 4의 최소공배수