高速素数列挙(ExactDiv)
(math/prime/get_prime2.cpp)

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

説明

線形篩で n 以下の素数を列挙する。 素数は ExactDiv<uint> として保持し、除算判定を高速化できる形で返す。 計算量は $O(n)$。

できること

• vector<ExactDiv<uint>> get_prime_exact_div(int n) n 以下の素数を返す。n <= 1 なら空
• bool ExactDiv<T>::divide(T x) const x がこの素数で割り切れるかを返す

使い方

LinearSieve の素数列挙を ExactDiv<uint> に詰め直した wrapper である。 返り値の各要素は素数値を val に持つ。 試し割りを大量に行うコードでは x % p == 0 の代わりに p.divide(x) を使える。

Depends on

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

Verified with

• test/aoj_alds1_1_c_get_prime2.test.cpp

Code

#include "linear_sieve.cpp"

template<typename T>
struct ExactDiv {
    T t, i, val;
    ExactDiv() {}
    ExactDiv(T n) : t(T(-1) / n), i(mul_inv(n)) , val(n) {};
    T mul_inv(T n) {
        T x = n;
        for (int i = 0; i < 5; ++i) x *= 2 - n * x;
        return x;
    }
    bool divide(T n) const {
        if(val == 2) return !(n & 1);
        return n * this->i <= this->t;
    }
};

vector<ExactDiv<uint>> get_prime_exact_div(int n) {
    vector<ExactDiv<uint>> res;
    auto primes = LinearSieve(n).primes;
    res.reserve(primes.size());
    for (auto &&p : primes) res.emplace_back((uint)p);
    return res;
}
const auto primes = get_prime_exact_div(32000);

#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_prime2.cpp"

template<typename T>
struct ExactDiv {
    T t, i, val;
    ExactDiv() {}
    ExactDiv(T n) : t(T(-1) / n), i(mul_inv(n)) , val(n) {};
    T mul_inv(T n) {
        T x = n;
        for (int i = 0; i < 5; ++i) x *= 2 - n * x;
        return x;
    }
    bool divide(T n) const {
        if(val == 2) return !(n & 1);
        return n * this->i <= this->t;
    }
};

vector<ExactDiv<uint>> get_prime_exact_div(int n) {
    vector<ExactDiv<uint>> res;
    auto primes = LinearSieve(n).primes;
    res.reserve(primes.size());
    for (auto &&p : primes) res.emplace_back((uint)p);
    return res;
}
const auto primes = get_prime_exact_div(32000);

Back to top page