C언어; 최대공약수 구하기 총정리 (4가지 방법)

 

 

1. 최대공약수를 구하는 방법

1) 약수를 이용하여 구하기

2) 두 수의 차이를 이용하여 구하기

3) 유클리드 호제법을 이용하여 구하기

4) 소인수분해를 이용하여 구하기

2. 방법 별 구현 코드 예시

1-1) 약수를 이용한 방법

int a, b, tmp;
scanf("%d %d", &a, &b);

for (int i = 2; i <= a && i <= b; i++)
{
    if (a % i == 0 && b % i == 0) tmp = i;
    else tmp = 1;
}
printf("%d", tmp);

두 수 중에서 작은 수 까지 반복문을 실행한다. 그 이유는 두 수의 공약수는 항상 두 수 중 작은 수의 약수 중에서 존재하기 때문이다. (ex. 18의 약수는 1,2,3,6,9,18 이고, 6의 약수는 1,2,3,6 이다. 이떄 18의 약수 중에서 9와 18은 6(18과 6 중 작은 수)의 약수에 없으므로 공약수가 될 수 없다.)

두 수의 공약수로 그 수를 나누면 나누어 떨어진다. 이것으로 판별하여 tmp에 작은 값부터 차례대로 입력되므로 반복문이 끝나면 tmp는 최대공약수가 저장 될 것이다. 만약 두 수를 나누어 떨어지게하는 수가 없다면, 1을 tmp에 입력한다.

 

2) 두 수의 차이를 이용한 방법

위 에서 a와 b는 서로소이다.

위를 통해서 A-B (두 수의 차)는 G(최대공약수)의 배수이다. 그러므로 A-B의 약수 중에서 G(최대공약수)가 있다.

설명한대로 코드를 작성해보겠다.

두 수 a와 b중 큰 값에서 작은수를 빼야한다. 이 동작을 두 수가 같아 질 때까지 반복하면 2개의 케이스가 발생한다. 첫번째는 두 수가 1이 아닌 최대공약수로 같을 때이고, 두번째는 두 수가 1로 같을 때이다.

int a, b;
scanf("%d %d", &a, &b);

while (a != b)
{
    if (a >= b) a -= b;
    else b -= a;
}

printf("%d\n", a);

 

3) 유클리드 호제법을 이용한 방법

두 자연수 A와 B(A ≥ B)일 때,

A ÷ B=q ··· r (q≠0)에서 A=Bq+r (0≤ r 〈 B)이다.

따라서, 두 수 A와 B의 최대공약수는 Bq+r와 B의 최대공약수와 동치이다.

Bq는 B의 배수이고, r은 B의 배수가 아니다. 그러므로 A와 B의 최대 공약수는 B와 r의 최대공약수라고 할 수 있다.

정리) A와 B의 최대공약수는 A를 B로 나눈 나머지가 r 일 때, B와 r의 최대공약수와 같음. (단, A ≥ B)

아래 참고. (k는 임의의 몫.)

b[0] b[1]

b[0]/b[1]=k ··· b[2]
b[1]/b[2]=k ··· b[3]
b[2]/b[3]=k ··· b[4]
        ⋮
b[n]/b[n+1]=k ... b[n+2]

b[n+2]==0 -> GCD: b[n+1]
b[n+2]==1 -> GCD: 1

-------------------------

b[0] b[1]

b[2]=b[0]%b[1]
b[3]=b[1]%b[2]
        ⋮
b[n+2]=b[n]%b[n+1]

b[n+2]==0 -> GCD: b[n+1]
b[n+2]==1 -> GCD: 1

아래 코드는 위의 구상을 토대로 보기 편하게 작성해 보았다.

int a[5] = {};

scanf("%d %d", &a[0], &a[1]);

int i = 0;
while (1)
{
    a[i + 2] = a[i] % a[i + 1];

    if (a[i + 2] == 0)
    {
        printf("%d\n", a[i + 1]);
        break;
    }
    if (a[i + 2] == 1)
    {
        printf("%d\n", a[i + 2]);
        break;
    }
    i++;
}

 

4) 소인수분해를 이용한 방법

72와 90을 소인수분해하면 다음과 같다.

이때 최대공약수는 두 수의 공통인 소수를 모조리 선택하여 곱한 값이다.

즉, 72와 90의 최대공약수는 2X3^2=18이다.

int isPrime(int n)
{
    if (n <= 1)
        return 0;
    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

int primeFactorization(int n, int factors[])
{
    int index = 0;
    for (int i = 2; i <= n; ++i)
    {
        while (n % i == 0 && isPrime(i))
        {
            factors[index++] = i;
            n /= i;
        }
    }
    return index;
}

int gcd(int a, int b)
{
    int factors_a[100] = {0};
    int factors_b[100] = {0};
    int cnt_a = primeFactorization(a, factors_a);
    int cnt_b = primeFactorization(b, factors_b);

    int gcd = 1;

    int i = 0, j = 0;
    while (i < cnt_a && j < cnt_b)
    {
        if (factors_a[i] == factors_b[j])
        {
            gcd *= factors_a[i];
            i++;
            j++;
        }
        else if (factors_a[i] < factors_b[j])
            i++;
        else
            j++;
    }

    return gcd;
}

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);

    int result = gcd(a, b);
    printf("%d\n", result);

    return 0;
}

3. 구현한 코드별 실행 시간 비교

2121212121와 1212121212의 최대공약수를 각 코드마다 5번 실행시 걸리는 시간의 평균

 

1) 약수를 이용하여 구하기 ⇒ 평균 3800ms

2) 두 수의 차이를 이용하여 구하기 ⇒ 평균 2.6ms

3) 유클리드 호제법을 이용하여 구하기 ⇒ 평균 3ms

4) 소인수분해를 이용하여 구하기 ⇒ 평균 67.4ms