C++で10^18までの大きな整数を素因数分解し、出現回数を求める方法

問題概要

この問題では、10¹⁸以下の整数 N が与えられ、その素因数とそれぞれの出現回数（指数）をすべて出力することが求められます。

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

入力：100
出力：2 2
　　　5 2
説明：100 の素因数分解は 100 = 2 × 2 × 5 × 5 となります。

解き方のアプローチ

この問題を解くには、まず対象の数の素因数をすべて求め、その後それぞれの素因数が出現する回数を数える必要があります。手順は以下の通りです。

• まず、2 が因数として何回含まれるかを確認し、割り切れる限り数を 2 で割り続けます。
• 次に、3 から √n までの奇数を順に調べ、その数の因数となる素数が見つかるたびに割り算を行い、出現回数をカウントします。
• 数が 1 になった時点で処理を終了します。
• 最後に、すべての素因数とその出現回数を出力します。

ポイントとして、√n より大きい素因数は高々 1 つしか存在しないため、ループ終了後に n が 2 より大きければ、その値自体が最後の素因数として残っていることになります。

実装例

以下のコードは、上記の解法を実装したものです。

#include <iostream>
#include <math.h>
using namespace std;
void factorize(long long n){
    int count = 0;
    while (!(n % 2)) {
        n/= 2;
        count++;
    }
    if (count)
        cout<<2<<"\t"<<count<<endl;
    for (long long i = 3; i <= sqrt(n); i += 2) {
        count = 0;
        while (n % i == 0) {
            count++;
            n = n / i;
        }
        if (count)
        cout<<i<<"\t"<<count<<endl;
    }
    if (n > 2)
    cout<<n<<"\t"<<1<<endl;
}
int main() {
    long long N = 21000;
    cout<<"The prime factors and their frequencies of the number "<<N<<" are \n";
    factorize(N);
    return 0;
}

出力結果

The prime factors and their frequencies of the number 21000 are
2   3
3   1
5   3
7   1

計算量について

この手法は「試し割り法」と呼ばれる古典的な素因数分解アルゴリズムで、計算量は O(√n) となります。10¹⁸ 程度の大きな整数でも、√(10¹⁸) = 10⁹ 回程度の演算で処理できるため、C++のような高速な言語であれば現実的な時間で素因数分解が可能です。また、偶数を先に取り除いた後は奇数のみを試すことで、さらに約半分の計算量に抑えられる点も工夫されています。