素因数分解

概要

正の整数を素因数分解する．最初に素数リストを作っておくと少し速くなる．素数表を使ったときの計算量は素数定理を参照．

計算量

素で $O(\sqrt n)$．素数表を用いると $O(\sqrt{n}/\log n)$ くらい．

使い方

$n$ を素因数分解し，素因数(first)とその指数(second)の vector のペアを返す．

実装

std::pair<std::vector<ll>, std::vector<ll>> prime_factor_decomp(ll n) {
    std::vector<ll> p, e;
    ll m = n;
    for (ll i = 2; i * i <= n; i++) {
        if (m % i != 0) continue;
        int c = 0;
        while (m % i == 0) c++, m /= i;
        p.push_back(i);
        e.push_back(c);
    }
    if (m > 1) {
        p.push_back(m);
        e.push_back(1);
    }
    return std::make_pair(p, e);
}

//@require eratosthenes.cc
std::pair<std::vector<ll>, std::vector<ll>> prime_factor_decomp_fast(ll n) {
    static const auto ps = make_primes(32000);  // sqrt(10^9)
    std::vector<ll> p, e;
    ll m = n;
    for (auto &i : ps) {
        if (i * i > n) break;
        if (m % i != 0) continue;
        int c = 0;
        while (m % i == 0) c++, m /= i;
        p.push_back(i);
        e.push_back(c);
    }
    if (m > 1) {
        p.push_back(m);
        e.push_back(1);
    }
    return std::make_pair(p, e);
}