C++로 숫자가 정확히 4개의 서로 다른 약수를 갖는지 확인하는 쿼리 문제 풀이

이 문제에서는 Q개의 쿼리가 주어지고, 각 쿼리마다 하나의 숫자 N이 포함됩니다. 우리가 해결해야 할 과제는 C++로 프로그램을 작성하여, 각 쿼리의 숫자가 정확히 4개의 서로 다른 약수(distinct factors)를 가지는지 판별하는 것입니다.

문제 설명

각 쿼리에 대해 숫자 N의 서로 다른 약수가 정확히 4개인지 확인합니다. 조건을 만족하면 YES를, 만족하지 않으면 NO를 출력합니다.

예시를 통해 문제를 살펴보겠습니다.

입력: Q = 3, 쿼리 = {4, 6, 15}

출력: NO YES YES

풀이 설명

쿼리 1: 4의 약수는 1, 2, 4로 총 3개이므로 NO입니다.

쿼리 2: 6의 약수는 1, 2, 3, 6으로 총 4개이므로 YES입니다.

쿼리 3: 15의 약수는 1, 3, 5, 15로 총 4개이므로 YES입니다.

방법 1: √N까지 반복하며 약수 개수 세기

가장 직관적인 해결책은 숫자의 모든 약수를 직접 세는 것입니다. 약수는 항상 (i, N/i) 형태의 쌍으로 나타나므로, 1부터 √N까지의 수 중 N을 나누어 떨어지게 하는 수를 찾을 때마다 카운터를 2씩 증가시키면 됩니다. 탐색이 끝난 후 카운터 값이 4인지 검사하여 결과를 출력합니다.

#include <iostream>
#include <math.h>
using namespace std;

int solveQuery(int N){
    int factors = 0;
    for(int i = 1; i < sqrt(N); i++){
        if(N % i == 0){
            factors += 2;
        }
    }
    if(factors == 4){
        return 1;
    }
    return 0;
}

int main() {
    int Q = 3;
    int query[3] = {4, 6, 15};
    for(int i = 0; i < Q; i++){
        if(solveQuery(query[i]))
            cout<<"The number "<<query[i]<<" has exactly four distinct factors\n";
        else
            cout<<"The number "<<query[i]<<" does not have exactly four distinct factors\n";
    }
}

출력

The number 4 does not have exactly four distinct factors
The number 6 has exactly four distinct factors
The number 15 has exactly four distinct factors

참고: 이 방법은 완전제곱수(예: 16, 36)를 다룰 때 주의가 필요합니다. 완전제곱수의 경우 √N 자체도 약수이지만 짝이 되는 다른 약수가 없으므로, i × i == N일 때는 카운터를 1만 증가시키도록 예외 처리를 추가해야 정확한 결과를 얻을 수 있습니다.

방법 2: 정수론을 활용한 효율적 접근

더 효율적인 방법은 정수론의 성질을 이용하는 것입니다. 어떤 수가 정확히 4개의 서로 다른 약수를 가지려면 다음 두 경우 중 하나에 해당해야 합니다.

소수의 세제곱인 경우: N = p³이라면 약수는 1, p, p², N으로 정확히 4개입니다. 예를 들어 8 = 2³의 약수는 1, 2, 4, 8입니다.
서로 다른 두 소수의 곱인 경우: N = p₁ × p₂라면 약수는 1, p₁, p₂, N으로 역시 정확히 4개입니다. 예를 들어 15 = 3 × 5의 약수는 1, 3, 5, 15입니다.

따라서 에라토스테네스의 체(sieve of Eratosthenes)로 범위 내 모든 소수를 미리 구한 뒤, 위 두 형태에 해당하는 수를 배열에 미리 표시해 두면 각 쿼리를 O(1) 시간에 처리할 수 있습니다. 쿼리 개수가 많을 때 특히 유용한 방식입니다.

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

int N = 1000;
bool hasFourFactors[1000];

void fourDistinctFactors() {
    bool primeNo[N + 1];
    memset(primeNo, true, sizeof(primeNo));
    for (int i = 2; i <= sqrt(N); i++) {
        if (primeNo[i] == true) {
            for (int j = i * 2; j <= N; j += i)
                primeNo[j] = false;
        }
    }

    vector<int> primes;
    for (int i = 2; i <= N; i++)
        if (primeNo[i])
            primes.push_back(i);

    memset(hasFourFactors, false, sizeof(hasFourFactors));

    for (int i = 0; i < primes.size(); ++i) {
        int p1 = primes[i];
        if (1 * (pow(p1, 3)) <= N)
            hasFourFactors[p1*p1*p1] = true;
        for (int j = i + 1; j < primes.size(); ++j) {
            int p2 = primes[j];
            if (1 * p1*p2 > N)
                break;
            hasFourFactors[p1*p2] = true;
        }
    }
}

int main() {
    int Q = 3;
    int query[] = {3, 6, 15};
    fourDistinctFactors();
    for(int i = 0; i < Q; i++){
        if(hasFourFactors[query[i]])
            cout<<"The number "<<query[i]<<" has exactly four distinct factors\n";
        else
            cout<<"The number "<<query[i]<<" does not have exactly four distinct factors\n";
    }
    return 0;
}

출력

The number 3 does not have exactly four distinct factors
The number 6 has exactly four distinct factors
The number 15 has exactly four distinct factors

마무리

약수 개수를 직접 세는 방법은 구현이 간단하지만 쿼리마다 O(√N)의 시간이 소요되는 반면, 정수론적 성질과 소수 체를 활용하면 전처리 이후 각 쿼리를 상수 시간에 처리할 수 있습니다. 따라서 쿼리 수가 많은 상황에서는 두 번째 방법이 훨씬 효율적입니다.