【C++】数がちょうど4つの異なる約数を持つかどうかを判定するクエリ問題の解法

この記事では、Q個のクエリが与えられ、各クエリに数Nが含まれるという問題を扱います。C++を用いて、各数Nが「ちょうど4つの異なる約数」を持つかどうかを効率的に判定するプログラムを作成していきましょう。

問題の概要

各クエリに対して、数Nの約数がちょうど4個であるかを調べます。4個であれば「YES」、そうでなければ「NO」を出力してください。

入力例： Q = 3、クエリ： 4, 6, 15

出力例： NO YES YES

出力の解説

• クエリ1（N = 4）： 4の約数は 1, 2, 4 の3個なので「NO」
• クエリ2（N = 6）： 6の約数は 1, 2, 3, 6 の4個なので「YES」
• クエリ3（N = 15）： 15の約数は 1, 3, 5, 15 の4個なので「YES」

解法アプローチ①：全ての約数を数える方法

最もシンプルな解法は、数の約数をすべて列挙することです。約数は必ずペア（i と N/i）で現れるため、1から√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

解法アプローチ②：数論を活用した効率的な方法

約数を4つ持つ数には、次のような明確な特徴があります。この性質を利用すると、事前計算によって各クエリにO(1)で回答できるようになります。

• 素数の3乗である場合： N = p³（pは素数）のとき、約数は 1, p, p², N の4個になります。
• 異なる2つの素数の積である場合： N = p₁ × p₂（p₁ ≠ p₂）のとき、約数は 1, p₁, p₂, N の4個になります。

実装では、エラトステネスの篩であらかじめ素数を列挙し、上記の条件に当てはまる数にフラグを立てておきます。

実装例

#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

まとめ

√Nまで探索して約数を数える方法は直感的で実装も簡単ですが、クエリ数が多い場合には計算量がボトルネックになります。一方、「素数の3乗」または「異なる2つの素数の積」という数論的な性質を使った前計算方式なら、大量のクエリにも高速に対応できます。データの範囲やクエリ数に応じて、適切な解法を選択することが重要です。