[백준 C++] 5618. 공약수

문제 링크

문제

자연수 n개가 주어진다. 이 자연수의 공약수를 모두 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 2 또는 3이다. 둘째 줄에는 공약수를 구해야 하는 자연수 n개가 주어진다. 모든 자연수는 108 이하이다.

출력

입력으로 주어진 n개 수의 공약수를 한 줄에 하나씩 증가하는 순서대로 출력한다.

예제 입력 / 출력

// 예제 입력 1
2
75 125

// 예제 출력 1
1
5
25

// 예제 입력 2
3
110 22 88

// 예제 출력 2
1
2
11
22

// 예제 입력 3
3
66 11 3

// 예제 출력 3
1

풀이

📍 알고리즘

• 숫자들 중 가장 작은 수를 구한뒤 1부터 그 수까지 증가시키면서 동시에 나눗셈 나머지가 0이 되는 숫자를 구하면 그 숫자가 공약수이다.

#include <iostream>
#include <vector>

using namespace std;

int main(void) {

	int n, temp, min = 100000000;
	vector<int> num;

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> temp;
		num.push_back(temp);
	}

	for (int i = 0; i < num.size(); i++) {
		if (min > num[i]) min = num[i];
	}

	for (int i = 1; i <= min; i++) {
		if (n == 2) {
			if (num[0] % i == 0 && num[1] % i == 0) cout << i << "\n";
		}
		else {
			if (num[0] % i == 0 && num[1] % i == 0 && num[2] % i == 0) cout << i << "\n";
		}
	}

}