최대공약수(GCD)란?

어떤 두 수 이상의 공통인 약수를 그 수들의 공약수라 하고 공약수들 중 가장 큰 수를 최대공약수라 한다.

공약수는 최대공약수의 약수가 된다. 예를 들어 8의 약수는 1, 2, 4, 8이고 12의 약수는 1, 2, 3, 4, 6, 12이므로 8과 12의 공약수는 1, 2, 4 세 개이고 8과 12의 최대공약수는 공약수 중 가장 큰 수인 4이다.

최소공배수(LCM)란?

어떤 두 수 이상의 공통인 배수를 그 수들의 공배수라 하고 공배수들 중 가장 작은 수를 최소공배수라 한다. 공배수는 최소공배수의 배수가 된다. 예를 들어 8의 배수는 8, 16, 24, 32, 40, 48.... 이고 12의 배수는 12, 24, 36, 48, 60... 이므로 8과 12의 공배수는 24, 48... 이고 8과 12의 최소공배수는 공배수 중 가장 작은 수인 24이다.

코드1

int gcd_get(int x, int y)
{
    int i, ans;
    for (i = 1; i <= x; i++)
    {
        if (x % i == 0 && y % i == 0)
        {
            ans = i;
        }
    }
    return ans;
}
 
int main()
{
    .....
    gcd = gcd_get(a, b);
    lcm = a * b / gcd;
    .....
}

코드분석

gcd_get(int x, int y) 함수는 두 개의 수를 x와 y로 전달받아 최대공약수를 리턴해주는 함수이다.

1부터 두 수중 한 개의 값(x)까지 모두 확인하면서 두 수의 공약수인지 확인하여 저장해 두었다가 그 값을 리턴하게 된다.

공약수 중 맨 마지막 값이 저장되므로 그 수가 최대공약수가 된다.

최소공배수(lcm)는 별도의 함수를 작성하여 구할 수도 있겠지만 두 수의 최대공약수를 알고 있다면 다음의 규칙을 이용하여 쉽게 구할 수 있다.

두 수의 곱은 그 두수의 최대공약수와 최소공배수의 곱과 같다.

a와 b의 최대공약수를 gcd(a, b), a와 b의 최소공배수를 lcm(a, b)라 하면 a * b = gcd(a, b) * lcm(a, b) 따라서 두 수의 최대공약수를 알 경우 최소공배수는 두 수의 곱을 최대공약수로 나눈 몫을 구하면 된다. (lcm = a * b / gcd)

이 문제의 경우 x의 값이 최대 10000이므로 전혀 문제가 발생할 것이 없지만 만약 x의 값이 1억 이상의 큰 수라면 속도가 늦어질 수 있으므로 시간을 줄이기 위해 추가 작업이 필요하다.

시간을 줄이기 위한 방법을 몇 가지 살펴보도록 하자.

1) 1부터 x와 y중 작은 수까지만 살펴보면 조금은 줄일 수 있지만 큰 도움이 되지는 않는다.

2) 두 수중 한 개 수에 대한 약수를 모두 구한 후, 그 약수들 중 다른 한 개 수의 약수가 되는 최대값을 구한다. 제곱근 만큼만 반복해서 모든 약수를 구하는 방법은 앞에서 익힌 바 있다.

3) 프로그램에서 최대공약수를 가장 빠르고 간단하게 구하는 방법은 아래에 소개하는 유클리드 호제법을 이용하는 것이다.

유클리드 호제법(Euclidean algorithm) :

A를 B로 나눈 나머지가 r이라면 A와 B의 최대공약수는 B와 r의 최대공약수와 같다. GCD(A, B) = GCD(B, r) 이 원리를 이용하면 두 수의 최대공약수를 간단하게 구할 수 있다.

이 방법으로 30과 18의 최대공약수를 구하는 과정을 살펴보면 다음과 같다.

GCD(30, 18) = GCD(18, 12) = GCD(12, 6) = 6 * 30을 18로 나눈 나머지는 12, 18을 12로 나눈 나머지는 6, 12를 6으로 나눈 나머지는 0이므로, 30과 18의 최대공약수는 12와 6의 최대공약수인 6과 같다.

코드2는 유클리드 호제법을 이용하여 최대공약수를 구하는 함수이다.

코드3은 같은 내용을 재귀함수를 이용하여 더 간단하게 구현한 것이다.

최대공약수나 최소공배수등과 관련된 문제를 해결하기 위해 항상 편리하게 활용할 수 있으므로 잘 익혀두는 것이 좋다.

코드2

int gcd_get(int x, int y)
{
    int r;
    while (y!=0)   // y 0이면 x가 최대공약수이므로 종료한다.
    {
        r = x % y; // 나머지를 구한후
        x = y; // x를 y로
        y = r; // y를 r로 바꾸고 다시 반복한다.
    }
    return x; // 최대공약수를 리턴한다.
}

코드3

int gcd_get(int x, int y)
{
    if(y == 0) return x; // y 0이면 x가 최대공약수이다.
    return gcd_get(y, x % y); // x와 y의 최대공약수는 y와 x % y 의 최대공약수와 같다.
}

#1658 upload 8270 done 4957 how_to_reg 4179

Greatest Common Divisor and Least Common Multiple timer 1s memory 64MB

#1658

Greatest Common Divisor and Least Common Multiple 1s 64MB