C++로 1부터 N까지 거의 소수(Almost Prime) 개수 구하기

자연수 N이 주어졌을 때, 1부터 N 사이에 존재하는 거의 소수(almost prime)의 개수를 구하는 것이 목표입니다. 거의 소수란 서로 다른 소인수를 정확히 두 개 가지는 수를 의미합니다. 이때 소수가 아닌 약수는 몇 개가 있더라도 상관없으며, 핵심은 서로 다른 소수 인수가 정확히 두 개여야 한다는 점입니다.

예를 들어 N이 10이라면 정답은 2입니다. 해당 범위에서 조건을 만족하는 수는 6(= 2 × 3)과 10(= 2 × 5) 두 개뿐이기 때문입니다.

접근 방법 – 에라토스테네스의 체 활용

이 문제는 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하면 효율적으로 해결할 수 있습니다. 먼저 체를 이용해 충분한 범위까지의 소수 여부를 미리 계산해 둔 뒤, 각 수마다 소인수가 정확히 두 개인지 검사하는 방식입니다.

소인수를 셀 때는 √i까지만 확인하면 충분합니다. i의 약수 j를 찾으면 짝이 되는 약수 i/j도 반드시 존재하므로, j와 i/j가 각각 소수인지 검사하여 개수를 더해 주면 됩니다. j × j = i인 제곱수의 경우에는 j 하나만 확인하면 됩니다. 또한 서로 다른 두 소인수를 가질 수 있는 가장 작은 수는 6(= 2 × 3)이므로, 검사를 6부터 시작하면 불필요한 연산을 줄일 수 있습니다.

C++ 구현 예제

#include<iostream>
#define N 100005
using namespace std;
bool prime[N];
void SieveOfEratosthenes() {
    for(int i = 0; i<N; i++)
        prime[i] = true;
    prime[1] = false;
    for (int i = 2; i * i < N; i++) {
        if (prime[i] == true) {
            for (int j = i * 2; j < N; j += i)
                prime[j] = false;
        }
    }
}
int countAlmostPrime(int n) {
    int result = 0;
    for (int i = 6; i <= n; i++) {
        int div_count = 0;
        for (int j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                if (j * j == i) {
                    if (prime[j])
                        div_count++;
                } else {
                    if (prime[j])
                        div_count++;
                    if (prime[i / j])
                        div_count++;
                }
            }
        }
        if (div_count == 2)
            result++;
    }
    return result;
}
int main() {
    SieveOfEratosthenes();
    int n = 21;
    cout << "Number of almost primes in range 1 to "<<n << " is: " << countAlmostPrime(n);
}

실행 결과

Number of almost primes in range 1 to 21 is: 8

동작 원리 살펴보기

N = 21일 때 조건을 만족하는 수는 6, 10, 12, 14, 15, 18, 20, 21로 총 8개입니다. 여기서 12(= 2² × 3), 18(= 2 × 3²), 20(= 2² × 5)처럼 같은 소수가 거듭 곱해진 경우에도 서로 다른 소인수는 두 개이므로 거의 소수에 포함됩니다.

시간 복잡도를 살펴보면, 에라토스테네스의 체를 생성하는 데 O(N log log N)이 소요되고, 각 수의 소인수 검사에는 최대 O(√N)이 걸리므로 전체적으로 약 O(N√N)의 시간 복잡도를 가집니다.