【C++入門】数値の素因数分解：すべての素因数とその指数（べき乗）を効率的に出力する方法

この記事では、「整数 N が与えられたとき、その数を割り切るすべての異なる素因数と、それぞれの指数（べき乗）を求めて出力する」という問題を、C++ を使って効率的に解く方法を解説します。

問題の概要

まず、具体例を見てみましょう。

入力：55
出力：
5 の指数：1
11 の指数：1

解説：
55 は 5 × 11 と素因数分解できます。どちらの素因数も 1 回しか現れないため、それぞれの指数は 1 となります。

解法のアプローチ

この問題に対する基本的なアプローチは以下の通りです。

1. N の素因数を見つける。
2. 各素因数が N を何回割り切れるか（＝指数）を数える。
3. 結果を出力する。

ここでは、最小素因数テーブル（sieve）を事前に構築しておくことで、高速に処理できる効率的な手法を紹介します。

アルゴリズム（効率的なアプローチ）

Step 1: 配列 s[N+1] を用意する。
        s[i] = i を割り切る最小の素因数。
Step 2: prime = s[N]、power = 1 として初期化する。
Step 3: while (N > 1) の間、以下を繰り返す：
    Step 3.1: N /= s[N]
    Step 3.2: if (prime == s[N]) → power++
Step 4: prime と power を出力する。

このアルゴリズムでは、各数値について「それ自身を割り切る最小の素因数」を記録した配列を利用することで、N を素因数で順に割りながら指数をカウントできます。計算量はほぼ O(log N) で抑えられるため、大きな数でも高速に動作します。

C++ 実装例

#include<bits/stdc++.h>
using namespace std;
void primes(int N, int s[]){
    vector <bool> prime(N+1, false);
    for (int i=2; i<=N; i+=2)
        s[i] = 2;
    for (int i=3; i<=N; i+=2){
        if (prime[i] == false){
            s[i] = i;
            for (int j=i; j*i<=N; j+=2){
                if (prime[i*j] == false){
                    prime[i*j] = true;
                    s[i*j] = i;
                }
            }
        }
    }
}
void generatePrimeFactors(int N) {
    int s[N+1];
    primes(N, s);
    cout<<"Factor\tPower"<<endl;
    int prime = s[N];
    int power = 1;
    while (N > 1){
        N /= s[N];
        if (prime == s[N]){
            power++;
            continue;
        }
        cout<<prime<<"\t"<<power<<endl;
        prime = s[N];
        power = 1;
    }
}
int main() {
    int N = 55;
    cout<<"The prime factors are and their powers are :\n";
    generatePrimeFactors(N);
    return 0;
}

実行結果

The prime factors are and their powers are :
Factor Power
5 1
11 1

まとめ

本記事では、エラトステネスの篩に似た手法で「各数の最小素因数」を記録した配列を構築し、それをもとに N を順次割り進めることで、素因数とその指数を同時に求める方法を紹介しました。
この手法は試し割り法よりも効率的で、複数のクエリを扱う場合にも応用できるため、競技プログラミングなどでも役立つテクニックです。