[BOJ] 공약수 5618번 C++

 

 

문제

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

입력

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

출력

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

 

접근 방식

 

항상.. 수학 문제가 젤 어려운 것 같다

생각보다 접근 방식은 간단하다.

 

1. 주어진 N개의 숫자의 최대공약수를 먼저 찾는다.

2. 구한 최대공약수의 모든 약수를 찾아서 출력한다.

 

 

이때, 최대 공약수를 어떻게 구하는지가 관건이다.

최대 공약수는 유클리드 알고리즘을 사용하면 간단하게 구할 수 있다.

// 최대공약수를 구하는 함수 (유클리드 알고리즘 사용)
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

 

예시로 75와 125의 최대 공약수를 구하게 된다면

a b
75 125
125 75
75 50
50 25
25 0

 

의 과정을 거쳐 최대공약수인 25를 찾을 수 있다.

 

최대 공약수를 찾았다면, 약수를 찾을 차례이다..

 

void printDivisors(int n) {
    vector<int> divisors;
    // 1부터 sqrt(n)까지 순회하면서 약수를 찾음
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) { // i가 n의 약수인 경우
            divisors.push_back(i); // i를 추가
            if (i != n / i) { // 중복을 피하기 위해 추가 확인
                divisors.push_back(n / i); // n / i도 약수로 추가
            }
        }
    }
    // 약수를 오름차순으로 정렬
    sort(divisors.begin(), divisors.end());
    // 약수 출력
    for (int d : divisors) {
        cout << d << '\n';
    }
}

 

i가 1일때, 25/1 == 0 이므로 1도 약수이지만 25도 약수가 된다

 

 

 

코드

#include<bits/stdc++.h>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

void printDivisors(int n) {
    vector<int> divs;
    for(int i=1; i*i <= n ; i++) {
        if(n%i == 0) {
            divs.push_back(i);
            if(i != n/i) {
                divs.push_back(n/i);
            }
        }
    }
    sort(divs.begin(), divs.end());

    for(auto d : divs) cout<<d<<'\n';
}

int main() {
    int n; cin>>n;
    vector<int> nums(n);
    for(int i=0; i<n; i++) cin>>nums[i];

    int g = nums[0];

    for(int i=1; i<n; i++) {
        g = gcd(g, nums[i]);
    }

    printDivisors(g);
}