유클리드 알고리즘

최대공약수 (GCD)

• 주어지는 두 정수의 약수 중에서 가장 큰 공통 약수이다.
• 소인수분해를 통해 GCD를 구할 수 있다.
• 뻴셈 기반의 알고리즘이다.
• GCD(u,v) = GCD(u-v,v) if u > v
• GCD(u,0) = u

GCD(100,30) = GCD(70,30) = GCD(40,30) = GCD(10,30) = GCD(30,10)

= GCD(20,10) = GCD(10,10) = GCD(0,10) = 10

 

코드 구현하기

int get_gcd(int u, int v){

    int t;
    while(u){
    	if(u<v){ //u가 v보다 작으면 두 수를 바꾼다.
        	t = u;
            u = v;
            v = t;
        }
        u = u-v;
    }
    return v;
}

 

뺄셈 기반 알고리즘의 문제

 - u와 v의 값 차이가 클 때 많은 뺄셈을 요구한다.

 - 뺄셈의 결과는 나눗셈의 나머지를 구하는 것

 

임의의 두 정수 u,v에 대해 v가 0이 아니면

u = u%v.  -> 항상 u%v < v 여야한다.

u 와 v를 교환

이때 v가 0이면 u 가 GCD가 된다.

GCD(100,30) = GCD(10,30) = GCD(30,10) = GCD(0,10) = GCD(10,0) = 10

 

코드 구현하기

int get_gcd(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);
} // 재귀함수를 사용하여 풀이