[BOJ5618][C++] 공약수

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	3857	1932	1682	59.205%

문제

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

 

입력

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

 

출력

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

 

예제 입력 1

2  75 125

 

예제 출력 1

1  5  25

 

출처

Olympiad > 일본정보올림피아드 > 일본정보올림피아드 예선 > JOI 2006 모의고사 1 2번

• 문제를 번역한 사람: baekjoon
• 데이터를 추가한 사람: njw1204
• 알고리즘 분류
• 수학

 

---

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65

#include <iostream> #include <vector> using namespace std; vector<int> findGongYaksu(int num1, int num2); vector<int> findGongYaksu2(int num1, int num2, int num3); int main() { int N, *ary; vector<int> result; cin >> N; ary = new int[N]; for (int i = 0; i < N; i++) { cin >> ary[i]; } if (N == 2) { result = findGongYaksu(ary[0], ary[1]); } else if (N == 3) { result = findGongYaksu2(ary[0], ary[1], ary[2]); } else { return 0; } for (int num: result) { cout << num << endl; } free(ary); return 0; } vector<int> findGongYaksu(int num1, int num2) { int maxSize = (num1 > num2) ? num1 : num2; vector<int> result; for (int i = 1; i <= maxSize; i++) { if ((num1 % i == 0) && (num2 % i == 0)) { result.push_back(i); } } return result; } vector<int> findGongYaksu2(int num1, int num2, int num3) { int maxSize = num1; if (maxSize < num2) maxSize = num2; if (maxSize < num3) maxSize = num3; vector<int> result; for (int i = 1; i <= maxSize; i++) { if ((num1 % i == 0) && (num2 % i == 0) && (num3 % i == 0)) { result.push_back(i); } } return result; }

 

공약수를 구할 숫자들 중에서 최댓값을 구한 후, for문을 1부터 최댓값까지 돌려서 공약수를 구할 수들을 for문의 인자값과 모두 비교하면서 공통으로 나누어 떨어지는 수를 벡터에 넣어 출력하도록 했다.