[C++] 유클리드 호제법을 사용해 최대공약수 구하기

유클리드 호제법

유클리드 호제법이란 2개의 자연수를 이용해 최대공약수를 구하는 알고리즘이다.

 

유클리드 호제법을 사용해 최대공약수를 구하는 방법

• 두 자연수를 각각 a와 b라고 하고 a >= b 일 때
• a % b = c 계산을 한다.
• c가 0이 아니라면 b % c 계산을 진행한다.
• 나머지 값이 0이 될 때까지 반복한다.
• 나머지 값이 0이 되었을 때 나누는 수의 값이 두 자연수의 최대공약수이다.

 

예시) 78696와 19332의 최대공약수 구하기 / 최대공약수는 36이다.

78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
 1368 ＝ 180×7 ＋ 108
  180 ＝ 108×1 ＋ 72
  108 ＝ 72×1 ＋ 36
   72 ＝ 36×2 ＋ 0

출처) 위키백과

 

---

최대공약수 구하기

유클리드 호제법을 통해 최대공약수를 구하는 코드를 작성해 본다.

#include <iostream>
using namespace std;

int divisor(int x, int y) {		// 최대공약수
	int z = x % y;

	while (z != 0) {
		x = y;
		y = z;
		z = x % y;
	}
	return y;
}

int main() {
	int a, b, div, temp;
	cin >> a >> b;

	if (a < b) 					// a가 b보다 작을경우 a와 b의 값을 바꾼다.
	{
		temp = a;
		a = b;
		b = temp;
	}

	div = divisor(a, b);

	cout << "a의 값: " << a << " b의 값: " << b << endl;
	cout << div;

	return 0;
}

 

a의 값이 b보다 크거나 같아야 하므로 a가 b보다 작을 때 a와 b의 값을 바꾸는 코드를 추가하였다.

 

+) a의 값이 b보다 작은 경우

 

 

---

최소공배수 구하기

유클리드 호제법을 통해 최대공약수를 구했다면 최대공약수를 이용해 최소공배수도 구할 수 있다.

 

두 수의 곱 = 최대공약수 * 최소공배수이다.

 

따라서 최소공배수 = ( 두 수의 곱 ) / 최대공약수이다. 이를 통해 최소공배수를 구하는 코드를 작성해 본다.

#include <iostream>
using namespace std;

int divisor(int x, int y) {		// 최대공약수
	int z = x % y;

	while (z != 0) {
		x = y;
		y = z;
		z = x % y;
	}
	return y;
}

int multiple(int x, int y) {		// 최소공배수
	return (x * y) / divisor(x, y);
}

int main() {
	int a, b, div, mul, temp;	// div 최대공약수  mul 최소공배수
	cin >> a >> b;

	if (a < b) 			// a가 b보다 작을경우 a와 b의 값을 바꾼다.
	{
		temp = a;
		a = b;
		b = temp;
	}

	div = divisor(a, b);
	mul = multiple(a, b);

	cout << "a의 값: " << a << " b의 값: " << b << endl;
	cout << "최대공약수: " << div << ", 최소공배수: " << mul << endl;

	return 0;
}

 

결과)