高速な素因数分解

解説

まず、ある数字が持つ最小の素因数を持つ配列を作成します。
つまり、となっています。
このような配列は、最初に昇順に数字を入れておいた配列に対して、インデックスと、その要素が等しいところからエラトステネスの篩の要領でループを回すことで作成できます。

次に、上で作成した配列を用いて、ある数字を素因数分解することを考えます。
これは、今現在の値のもつ最小の素因数で割り続けることで実現できます。
この方法だと高々logオーダーで計算することが出来ます。

計算量は、最大の数をとすると篩を準備するフェーズでとなります。
また、素因数分解する数をとすると、で素因数分解出来ます。

コード

ABC177Eでverifyしました。
この問題では、個の数を素因数分解しているので最大の計算量は、となります。
Submission #18055027 - AtCoder Beginner Contest 177

struct SmartPrimeFactorize {
    vector<int> sieve;

    SmartPrimeFactorize(int Max_N) : sieve(Max_N + 1, 0) {
        //コンストラクタ中で篩を構築
        for (int i = 0; i <= Max_N; i++) sieve[i] = i;

        for (int i = 2; i * i <= Max_N; i++) {
            if (sieve[i] == i) {
                for (int j = i + i; j <= Max_N; j += i) {
                    sieve[j] = i;
                }
            }
        }
    }

    
    vector<int> prime_factorize(int n) {
        vector<int> fact;
        while (n != 1) {
            fact.push_back(sieve[n]);
            n /= sieve[n];
        }
        return fact; //素因数を列挙した配列を返す
    }
};