최대공약수(gcd), 최소공배수(lcm)

알고리즘 문제를 풀다보면 가끔 최대공약수, 최소공배수를 구하라는 문제가 나온다.

자주 있는 문제 유형이 아니다보니 항상 문제를 풀때마다 구하는 방법을 찾는 것 같아서

정리할 필요가 있어서 작성한다.

유클리드 공식이라고 하여 최대공약수에는 다음과 같은 성질이 있다.

• 0과 n의 최대공약수는 n이다
• a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다

위와 같은 성질이 있다고 한다.

이 공식을 토대로 코드를 작성하면 다음과 같다

 

int gcd(int a, int b){
    // 큰 숫자를 a에 둔다
    if(a < b){
        int t = a;
        a = b;
        b = t;
    }
    while(b!=0){
        int n = a % b;
        a = b;
        b = n;
    }
    return a;
}

 

작은 수가 0이 될때까지 반복을 하다보면 a와 0의 최대공약수가 나온다.

이 공약수가 최대공약수가 되도록 만든 것이다.

 

최소공배수는 다음과 같이 구한다.

• a와 b의 곱을 구한다
• 곱을 최대공약수로 나눈다

위와 같이 구하면 최소공배수가 된다.

 

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

 

최대공약수만 구하면 정말 간단한 함수가 된다.

 

간단하니까 잘 외워둬야겠다.