C++로 n의 모든 약수 출력하기 – 에라토스테네스의 체를 활용한 쿼리 문제 풀이

이번 글에서 다룰 문제는 주어진 정수 n의 모든 약수를 출력하는 것입니다.

입력: 15
출력: 1 3 5 15
설명
15의 약수는 1, 3, 5, 15입니다.

입력: 30
출력: 1 2 3 5 6 10 15 30

이 문제는 에라토스테네스의 체(Sieve of Eratosthenes)에서 사용하는 방식을 응용하면 효율적으로 해결할 수 있습니다.

문제 해결 접근 방법

에라토스테네스의 체와 동일한 개념을 적용하여 n의 약수를 구합니다. 미리 최대 범위까지 모든 수의 약수를 계산해 두면, 이후 쿼리가 들어올 때마다 약수를 새로 구할 필요가 없어 처리 속도가 크게 향상됩니다.

예제 코드

#include <bits/stdc++.h>
#define MOD 1000000007

using namespace std;

vector<int> divisors[100001]; // 각 숫자와 그 숫자의 모든 약수를 담는 벡터
void findsieve(int max) { // 10^5까지 divisors 벡터를 채웁니다
    for(int i = 1; i <= max; i++) {
        for(int j = i; j <= max; j += i)
            divisors[j].push_back(i);
    }
}
void __print(int n){ // 약수를 출력하는 함수
    for(auto x : divisors[n])
        cout << x << " ";
    cout << "\n";
}

int main() {
    findsieve(100000); // 10^5까지의 체와 약수를 미리 계산해 둡니다
    int n = 6; // 주어진 n
    __print(n);
    n = 30; // 새로운 n
    __print(n);
    return 0;
}

실행 결과

1 2 3 6
1 2 3 5 6 10 15 30

코드 설명

이 접근 방식은 에라토스테네스의 체와 같은 원리를 따릅니다. 10^5까지의 모든 수에 대해 각각의 약수를 미리 구해 저장해 둡니다. 체를 만드는 사전 계산에는 O(M log M)의 시간이 소요되지만(M은 최대 범위), 한 번만 계산해 두면 이후 q개의 쿼리를 처리할 때 약수를 다시 찾을 필요가 없으므로 전체 실행 시간이 크게 단축됩니다. 쿼리 처리 단계의 시간 복잡도는 O(Q × N)이며, 여기서 Q는 처리하는 쿼리의 개수, N은 n의 약수 개수입니다.

마무리

이번 글에서는 에라토스테네스의 체의 원리를 응용하여 n의 모든 약수를 출력하는 쿼리 문제를 해결해 보았습니다. C++로 작성된 완성된 프로그램과 함께 문제 해결의 전체적인 접근 방식도 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분에게 도움이 되었기를 바랍니다.