[C] 최대공약수 구하기 (유클리드 알고리즘)

[C] 최대공약수 구하기 (유클리드 알고리즘)

최대공약수(GCD : Greatest Common divisor)는 주어진 두 정수의 약수 중에서 가장 큰 공통되는 약수이다.

유클리드의 알고리즘은 최대공약수의 성질을 이용하여 뺄셈과 두 값의 교환이라는 기본적인 동작으로만 최대공약수를 구할 수 있다.

유클리드의 알고리즘으로 최대공약수를 구하는 방법은 다음과 같다.

1. 임의의 두 정수 u와 v를 입력 받는다.

2. v가 u보다 크다면 v와 u의 값을 교환한다.

3. u 에다 u-v의 값을 저장한다.

4. u가 0인가? 0이 아니면 2로 돌아간다.   0이면 v가 최대공약수이다.

// 뺄셈을 이용하는 방법
int gcd_minus(int u, int v){
    
    int t;
    while (u){
        if (u < v){
            t = u; u = v; v = t;
        }
        u = u - v;
    }
    return v;
}

위의 알고리즘은 두 수의 값 차이가 클 경우 그 만큼  뺄셈을 해야 된다.

%(나머지) 연산을 뺄셈 대신 사용하여, 알고리즘의 효율을 높일 수 있다.

1. 임의의 두 정수 u와 v를 입력받는다.

2. v가 0인가? 0이면 u가 최대공약수이다. 끝.

                0이 아니면 u에 u%v를 대입하고, u와 v의 값을 교환한다.

3. 2로 돌아간다.

// 나머지 연산을 이용하는 바법
int gcd_modulus(int u, int v){
    
    int t;
    while (v){
        t = u%v;
        u = v;
        v = t;
    }
    return u;
}

여기서 재귀 호출을 사용하면, 좀 더 간결한 코드가 된다.

// 재귀 호출을 이용하는 방법
int gcd_recursion(int u, int v){
    
    if (v == 0){
        return u;
    }
    else{
        return gcd_recursion(v, u%v);
    }
}

위 각각의 알고리즘을 실행하는 main 함수

#include <stdio.h>
    
void main(void){
    
    int u, v;

    puts("\n ECLID1 : Get GCD of two positive integer"
        "\n             Input 0 to end program");

    while (1){
        puts("\n\n Input two positive integer -> ");
        scanf_s("%d %d", &u, &v);
        if (u < 0 || v < 0)
            continue;
        if (u == 0 || v == 0)
            break;
        
        printf("\n   GCO_MINUS of %d and %d is %d.", u, v, gcd_minus(u, v));
        printf("\n   GCO_MODULUS of %d and %d is %d.", u, v, gcd_modulus(u, v));
        printf("\n   GCO_RECURSION of %d and %d is %d.", u, v, gcd_recursion(u, v));
    }

    return 0;
}

먼저 뺄셈을 이용한 알고리즘과 나머지 연산을 이용한 알고리즘을 비교하면,

두 정수의 값 차이가 클 경우 나머지 연산의 알고리즘이 연산의 횟수가 적으므로 더 효율적으로 동작한다.

재귀 호출의 경우 나머지 연산의 연산 횟수와 같지만, 같은 조건일 때 재귀 호출이 조금 더 많은 시간을 사용한다.

하지만 재귀 호출은 코드의 간결함과 가독성이 좋은 장점이 있다.

출처: https://hyeonstorage.tistory.com/336?category=622873 [개발이 하고 싶어요]