유클리드 호제법 알고리즘, 최대공약수, 최소공배수

개인 공부/알고리즘

_h.j 2021. 2. 16. 18:49

728x90

두 수의 최대 공약수를 구하는 알고리즘의 하나.

2개 자연수 a, b ( a > b )에 대해 a를 b로 나눈 나머지를 r이라 하면,

a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

또 다시 b , r 에 대해 b를 r로 나눈 나머지 r' 을 가지고 위의 과정을 반복해 나머지가 0이 되었을 때

나누는 수가 a와 b의 최대 공약수.

( a , b ) = ( b , r (=a%b) ) = ( r , r' )

( 1071 , 1029 ) = ( 1029 , 42 ) = ( 42 , 21 ) = ( 21 , 0 ) = 21

21은 1071과 1029의 최대 공약수

GCD 관련 법칙

1. a , b (a > b) 가 입력으로 들어온다.

2. b == 0 이면 a 리턴

3. 아니라면 b ,a%b 로 다시 반복

//recursive 
int GCD1(int a,int b){
	return b? GCD(b,a%b) : a;
}

int GCD2(int a, int b){
	int tmp;
	while(a%b){
		tmp = a/b;
		b = a%b;
		a = tmp;
	}
	return a;
}

정수의 경우

정수 m , n 의 최대 공약수 GCD(m,n) 구할 때 확장된 유클리드 호제법 이용하면

am + bn = GCD(m,n) 의 해되는 a,b 짝 찾을 수 있다.

최소공배수 구하기

//최소 공배수
int LCM(int a, int b){
	return a*b/GCD(a,b);
}

최악의 경우라도 작은 수(십진법) 자리수의 5배 반복하기 전에 최대공약수에 이른다(라메의 정리)

최대공약수 구할 때 소인수분해보다 유클리드 호제법으로 구하는 것이 더 빠름.

최대공약수 구하는 것은 쉬운 문제, 소인수 분해가 더 어려운 문제.

2개의 정수의 비트수를 n,

유클리드 알고리즘은 Θ(n) 회의 나눗셈으로 최대공약수 구할 수 있음.

728x90