C++でnのすべての約数を出力するクエリ処理の実装方法

この記事では、与えられた整数 n のすべての約数を出力する問題を解説します。

入力：15
出力：1 3 5 15
説明
15の約数は 1、3、5、15 です。

入力：30
出力：1 2 3 5 6 10 15 30

この問題では、エラトステネスの篩（ふるい）で使われる考え方を応用することで、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

コードの解説

このアプローチでは、エラトステネスの篩と同じ原理を使います。具体的には、1 から 10⁵ までの各整数 i について、その倍数すべてに i を約数として追加していきます。これにより、範囲内のすべての数の約数リストが事前に完成します。

q 個のクエリが与えられた場合でも、約数をその都度計算する必要がないため、時間計算量が大幅に削減されます。結果として、全体の計算量は O(Q×N) となります。ここで Q は処理するクエリの数、N は n の約数の個数です。

まとめ

本記事では、エラトステネスの篩の原理を応用して「n のすべての約数を出力するクエリ」問題を解きました。前計算によって複数クエリへの高速な対応が可能になる点がポイントです。同じプログラムは C、Java、Python など他の言語でも同様に実装できます。この記事が皆さんの学習に役立てば幸いです。