【C++】エラトステネスの篩で最小素因数を前計算し、複数クエリをO(log n)で高速に素因数分解する方法

本記事では、複数のクエリに対して高速に素因数分解を行うプログラムをC++で実装する方法を解説します。

一般的な素因数分解の手法では、1回の計算にO(√n)の時間がかかります。クエリの数が増えると、この計算コストが積み重なり、全体の処理時間が大幅に膨らんでしまうのが課題です。そこで、エラトステネスの篩（ふるい）を活用することで、1クエリあたりO(log n)という非常に高速な素因数分解を実現します。

基本概念のおさらい

解説に入る前に、重要な2つの概念を確認しておきましょう。

素因数分解とは

素因数分解とは、ある整数を素数のみの積の形で表すことです。ここで含まれるのは素数の因子だけであり、合成数（素数同士の積でできた数）を因子として扱うことはありません。例えば45214なら「2 × 13 × 37 × 47」と表せます。

エラトステネスの篩とは

エラトステネスの篩は、指定された範囲内のすべての素数を効率的に列挙する古典的なアルゴリズムです。本記事では、これを少し拡張し、各数値の「最小素因数（SPF: Smallest Prime Factor）」を前計算してテーブルに保存する形で利用します。

解法アプローチ

この問題の核心は次の手順にあります。

1. 対象の数を割り切れる最小の素因数を見つける。
2. その素因数を答えとして記録し、元の数をその因数で割って更新する。
3. 数が1になるまでこの処理を繰り返す。数が1になれば、それ以上の素因数は存在しないことを意味します。

ポイントは、最小素因数の探索を毎回ゼロから行わず、エラトステネスの篩で事前に構築したSPFテーブルを参照する点です。これにより、素因数を1つ取り出す操作がO(1)になり、素因数分解全体もO(log n)で完了します。

C++による実装例

以下は、この解法の動作を示すサンプルプログラムです。

#include <iostream>
using namespace std;
int primes[100001];

void sieveOfEratosthenes(int N) {
    N += 2;
    primes[1] = 1;
    for (int i = 2; i < N; i++)
        primes[i] = i;
    for (int i = 4; i < N; i += 2)
        primes[i] = 2;
    for (int i = 3; i * i < N; i++) {
        if (primes[i] == i) {
            for (int j = i * i; j < N; j += i)
                if (primes[j] == j)
                    primes[j] = i;
        }
    }
}

void findPrimeFactors(int num) {
    sieveOfEratosthenes(num);
    int factor;
    while (num != 1) {
        factor = primes[num];
        cout << factor << " ";
        num /= factor;
    }
}

int main() {
    int N = 45214;
    cout << "Prime factorization of the number " << N << " using sieve is ";
    findPrimeFactors(N);
    return 0;
}

出力結果

Prime factorization of the number 45214 using sieve is 2 13 37 47

コードのポイント解説

• 配列の初期化： 最初に primes[i] = i と設定し、「まだ約数が見つかっていない」状態を表します。
• 偶数の処理： 4以上の偶数については、先に最小素因数を2として一括登録することで、後続のループを効率化しています。
• 篩の更新条件： if (primes[j] == j) のチェックにより、すでにより小さい素因数が登録されている値は上書きされません。これにより、必ず最小の素因数が保持されます。
• 素因数の抽出： findPrimeFactors 関数では、SPFテーブルを参照しながら数を割り続けるだけでよいため、除算の回数は最大でもlog n回程度に収まります。

計算量のまとめ

前計算を一度行っておけば、以降のクエリはどれだけ多くても各O(log n)で処理できるため、クエリが大量にある競技プログラミングやシステム開発の場面で特に有効な手法です。