유클리드 호제법, 최대공약수 구하기, GCD [C++]

최소공배수보다 최대공약수가 정말 많이 쓰인다.

어차피 최대공약수를 알 수 있으면 최소공배수도 알 수 있다.

 

즉, 쓰이는 곳이 많다.

최소공배수 구하기, 최대공약수 구하기, 기약분수 구하기 등

 

여기서 만능공식이 있으니

그것이 바로

유클리드 호제법이다.

기본 형태는 이렇다.

나무위키

 

 

수학자가 증명한 것이 참이라고 가정하고 이용한다.

공학자는 증명보다는 활용을 하기에

하지만 굳이 증명하고 싶다면 말리지는 않는다.

 

 

즉, 작은 것으로 치환할 수 있다는 말이다.

만약 gcd함수를 불러온다면.. 그것보다 작은함수를 불러오는 건가..?

재귀같네??

라고 생각하면 생각이 깊은 사람 굿

 

---

 

아무튼 C++에서는 여러가지 방법으로 구현할 수 있다.

 

일반적으로 a>b를 가정하고 만들긴한다.

하지만 굳이 a>b를 가정해야하느냐? 라는 사람이 있기 마련이다.

 

아무튼 밑에 3가지로 구현해놨다. 골라서 쓰자.

 

int GCD(int a, int b)
{
    if(b==0)return a;
    else return GCD(b,a%b);
}

 

int GCD(int a,int b){
    while(1){
        int r = a%b;
        if(r==0) return b;
		
        a = b;
        b = r;
    }
}

 

int GCD(int a, int b){
    int c;
    //b == 0이 되는 순간은 c가 0일 때다. 즉, 그 당시에 나눴던 값이 최대공약수가 된다.
    while( b != 0){
        c = a%b; 
        a = b;
        b = c;
    }
    //b는 a에 할당되었으므로 a를 반환한다.
    return a;
}

 

위의 것을 골라서 쓰기 바란다.

---

 

과정을 설명해보자면

 

a를 b로 나눈다.   

-> 나눠지면 b가 최대공약수

->그렇지 않으면 r이 남는다.

 

그 b는 호제법 식의 a가 되고

그 r은 호제법 식의 b가 되어

다시 a를 b로 나눈다.

 

...

 

즉, r = 0이 되면 그 때 b가 최대공약수가 되는 것이다.