[Baekjoon/C++] 5618번 - 공약수

[백준] Baekjoon Online Judge

문제로 이동

 

문제

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

 

입력

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

 

출력

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

 

---

풀이

#include <iostream>
#include <algorithm>
using namespace std;

int n, arr[3];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  
    cin >> n;
    for (int i = 0; i < n; i++) cin >> arr[i];

    sort(arr, arr + n);

    for (int i = 1; i <= arr[0]; i++) {
        if (arr[0] % i == 0 && arr[1] % i == 0 && arr[2] % i == 0) cout << i << '\n';
    }

    return 0;
}

 브루트포스 알고리즘으로 문제를 풀었다. 이때 공약수는 입력 받은 수 중 가장 작은 수를 넘을 수 없으므로 탐색범위를 1부터 입력 받은 가장 작은 수까지로 설정하였다.