最小素因数テーブル(Min Factor Table)
(math/prime/get_min_factor.cpp)

• View this file on GitHub
• Last update: 2026-03-22 19:39:35+09:00

説明

0..n の最小素因数を線形篩で求める。

できること

• vector<int> get_min_factor(int n) min_factor[x] に x の最小素因数を入れた長さ n + 1 の配列を返す。min_factor[0] = 0, min_factor[1] = 1

使い方

x >= 2 の素因数分解は x = x / min_factor[x] を繰り返せばよい。 素数 p では min_factor[p] = p になる。

実装上の補足

前計算は $O(n)$、各クエリは素因数の個数ぶんだけ進む。 単発クエリには重いが、同じ上限以下を何度も分解する用途に向く。

Depends on

• 線形篩(Linear Sieve) (math/prime/linear_sieve.cpp)

Required by

• math/powk_all.cpp

Code

#include "linear_sieve.cpp"

vector<int> get_min_factor(int n) {
    return LinearSieve(n, true).min_factor;
}

/**
 * @brief 最小素因数テーブル(Min Factor Table)
 */

#line 1 "math/prime/linear_sieve.cpp"



struct LinearSieve {
    int n;
    vector<int> primes;
    vector<int> min_factor;
    vector<int> phi;
    vector<int> mobius;
    vector<bool> prime_table;

    explicit LinearSieve(int n, bool need_min_factor = false, bool need_phi = false, bool need_mobius = false)
        : n(n < 0 ? 0 : n),
          min_factor(need_min_factor ? this->n + 1 : 0),
          phi(need_phi ? this->n + 1 : 0),
          mobius(need_mobius ? this->n + 1 : 0),
          prime_table(need_min_factor ? 0 : this->n + 1, true) {
        if (!prime_table.empty()) {
            prime_table[0] = false;
            if (this->n >= 1) prime_table[1] = false;
        }
        if (!min_factor.empty() && this->n >= 1) min_factor[1] = 1;
        if (!phi.empty()) {
            phi[0] = 0;
            if (this->n >= 1) phi[1] = 1;
        }
        if (!mobius.empty()) {
            mobius[0] = 0;
            if (this->n >= 1) mobius[1] = 1;
        }
        for (int i = 2; i <= this->n; ++i) {
            bool prime = min_factor.empty() ? prime_table[i] : min_factor[i] == 0;
            if (prime) {
                if (!min_factor.empty()) min_factor[i] = i;
                if (!phi.empty()) phi[i] = i - 1;
                if (!mobius.empty()) mobius[i] = -1;
                primes.emplace_back(i);
            }
            for (auto &&p : primes) {
                long long x = 1LL * i * p;
                if (x > this->n) break;
                if (!prime_table.empty()) prime_table[x] = false;
                if (!min_factor.empty()) min_factor[x] = p;
                bool same = i % p == 0;
                if (!phi.empty()) phi[x] = same ? phi[i] * p : phi[i] * (p - 1);
                if (!mobius.empty()) mobius[x] = same ? 0 : -mobius[i];
                if (same) break;
            }
        }
    }

    bool is_prime(int x) const {
        if (x < 2 || x > n) return false;
        if (!min_factor.empty()) return min_factor[x] == x;
        return prime_table[x];
    }
};

/**
 * @brief 線形篩(Linear Sieve)
 */


#line 2 "math/prime/get_min_factor.cpp"

vector<int> get_min_factor(int n) {
    return LinearSieve(n, true).min_factor;
}

/**
 * @brief 最小素因数テーブル(Min Factor Table)
 */

Back to top page