[Algorithm] 유클리드 알고리즘 (GCD)

유클리드 알고리즘

- 주어진 두 수 사이에 존재하는 최대 공약수 (GCD) 구하는 알고리즘

- 자세한건 유클리드 호제법 참고

- gcd ( a, b ) == gcd ( b, r ) 이다. (a,b 자연수 / r은 a를b로 나눈 나머지)

 

원리

•  자연수 a, b가 주어짐 이때  a가 b보다 큰 값임

int a = 자연수
int b = 자연수

•  a 를 b로 나눈 나머지가 r 이면

int r;

r = a % b;

• r이 0이면 b가 최대 공약수(gcd) 이다.

if (r == 0)
	return b;

• 만약 r이 0이 아니면, a에 b값 넣고, b에 r값 넣고, 다시 두번째 부터 반복하면 된다.

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

 

공식

int gcd(int a, int b){
	int c;
    
	while(b != 0){
    		c = a % b;
    		a = b;
        	b = c;
    	}
    
	return a;
}

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;
    }
}

 

 

참고

 

c++에서는 #include <algorithm> 이용하면

std::gcd(x, y); 사용하면

알아서 큰값 작은값 구분하고 계산해서

x와 y의 최대 공약수 반환한다.