C++로 10⁶ 미만의 숫자 중 최소 소인수가 N인 수의 개수 구하기

소수 하나(예: num)가 주어졌을 때, 10⁶(1,000,000)보다 작은 수 가운데 최소 소인수가 num과 같은 숫자가 총 몇 개인지 구하는 것이 이 글의 목표입니다.

예시

입력 − num = 7
출력 − 개수 = 38095

입력 − num = 3
출력 − 개수 = 166667

예를 들어 최소 소인수가 3인 수는 3, 9, 15, 21처럼 3의 배수이면서 더 작은 소수인 2로는 나누어지지 않는 수들이며, 3 자신도 포함됩니다.

해결 접근 방식

이 문제는 에라토스테네스의 체(Sieve of Eratosthenes)를 변형한 방식으로 효율적으로 해결할 수 있습니다. 체를 한 번만 만들어 두면 어떤 소수에 대해서도 답을 상수 시간에 얻을 수 있어, 여러 소수에 대해 반복적으로 질의해야 하는 경우에 특히 유용합니다.

숫자 num을 입력받습니다.
i를 2부터 최댓값(MAX)까지 반복하면서 1씩 증가시킵니다.
루프 안에서 s_prime[i]가 0인지 확인합니다. 0이라면 i는 소수입니다.
j를 i * 2부터 시작해 j가 MAX 이하인 동안 i씩 증가시키는 내부 루프를 실행합니다.
s_prime[j]가 아직 0이라면, j의 최소 소인수는 i입니다.
s_prime[j]를 1로 표시하여 j가 소수가 아님을 나타냅니다.
s_count[i]를 1 증가시켜 최소 소인수가 i인 숫자의 개수를 셉니다.
결과를 출력합니다.

주의할 점은 최종 답을 출력할 때 s_count[N]에 1을 더한다는 것입니다. 그 이유는 소수 N 자신도 '최소 소인수가 N인 수'에 포함되기 때문입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
// 소수 판별과 개수 카운트를 위한 체(sieve)
int s_prime[MAX + 4] = { 0 }, s_count[MAX + 4] = { 0 };
void create_sieve(){
    // 1은 소수가 아니므로 미리 표시
    s_prime[1] = 1;
    // 체 생성
    for (int i = 2; i <= MAX; i++){
        // i가 소수인 경우
        if (s_prime[i] == 0){
            for (int j = i * 2; j <= MAX; j += i){
                // i가 j의 최소 소인수인 경우
                if (s_prime[j] == 0){
                    // j는 소수가 아님을 표시
                    s_prime[j] = 1;
                    // 최소 소인수가 i인 숫자 개수 카운트
                    s_count[i]++;
                }
            }
        }
    }
}
int main(){
    // 체 생성
    create_sieve();
    int N = 7;
    cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
    N = 3;
    cout << "Number of prime factors = " << (s_count[N] + 1) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −

Number of prime factors = 38095
Number of prime factors = 166667

정리

체를 활용하면 O(N log log N)의 시간 복잡도로 10⁶ 이하 모든 수의 최소 소인수 정보를 미리 계산해 둘 수 있습니다. 이후에는 각 소수에 대한 질의를 상수 시간에 처리할 수 있으므로, 동일한 범위에서 여러 번 질의가 발생하는 문제에서 매우 효과적인 기법입니다.