[백준/C++] 5618번: 공약수

문제

https://www.acmicpc.net/problem/5618

5618번: 공약수

---

문제 요약

자연수가 n개 주어졌을 때 이 자연수의 공약수를 모두 출력한다.

 

n은 2 또는 3이다.

---

코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, a, b, c, gcd;

// 유클리드 호제법으로 a, b의 최대 공약수 반환
int GCD(int a, int b) {
	while (b != 0) {
		int tmp = b;
		b = a % b;
		a = tmp;
	}
	return a;
}

int main() {
	cin >> n;

	if (n == 2) {
		cin >> a >> b;

		gcd = GCD(a, b);
	}
	else {
		cin >> a >> b >> c;

		gcd = GCD(a, GCD(b, c));
	}

	// 최대 공약수의 약수들 출력
	for (int i = 1; i <= gcd; i++) {
		if (gcd % i == 0) {
			cout << i << "\n";
		}
	}

	return 0;
}

---

코드 설명

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

 

두 수의 최대공약수를 구할 수 있다면, 세 수의 최대공약수를 구할 수 있다.

+ a, b, c의 최대공약수는 b, c의 최대공약수와 a의 최대공약수이다.

 

1. 유클리드 호제법을 통해 최대공약수를 구한다.

 

2. 최대공약수의 약수를 출력한다.

---

고찰

유클리드 호제법은 다음과 같은 성질을 이용한다.

 

GCD(a, b)

= GCD(b, a % b)

= GCD(a % b, b % a % b)

= ...

 

한쪽이 오른쪽 인자가 0이 되어 더이상 나누어지지 않으면 멈추고, 그 때의 왼쪽 인자가 최대공약수이다.

 

즉, 재귀 함수로 GCD를 더 쉽게 구현할 수 있다.

int GCD(int a, int b) {
	if (b == 0) return a;
	return GCD(b, a % b);
}