[c/c++/알고리즘]유클리드 호제법, 최대공약수와 최소공배수의 관계

유클리드 호제법이란?

2개의 자연수의 최대공약수를 구하는 알고리즘이다.

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

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

​

b를 r로 나눈 나머지 x를 구하고, 다시 r을 x로 나눈 나머지를 구하는 과정을 반복한다.

결국 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

​

예시

1925와 819의 최대공약수

1925%819=287 -> 819%287=245 -> 287%245=42 -> 245%42=35 -> 42%35=7 -> 35%7=0

====> 7이 최대 공약수!

 

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

 

최대공약수와 최대공배수의 관계

출처: NAVER 지식백과

int gcd(int a, int b) {  //최대공약수
	int c;
	while (b) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}
int lcd(int a, int b) {  //최소공배수
	return a * b / gcd(a, b);
}