Sieve
(math/sieve.hpp)

• View this file on GitHub
• Last update: 2026-10-26 01:59:35+09:00
• Include: #include "math/sieve.hpp"

概要

• $n$ 以下の整数の最小素因数表を作り、素数判定・素因数分解・約数列挙をする。

使い方

• sieve(n): $n$ 以下の最小素因数表を作る。
• is_prime(x): $x$ が素数かを返す。
• smallest_prime_factor(x): $x$ の最小の素因数を返す。
• primes(): $n$ 以下の素数を昇順に返す。
• factorize(x): $x$ の素因数分解を (素因数, 指数) の列で返す。素因数の昇順。
• divisors(x): $x$ の約数を昇順に返す。

制約

• $1 \le n$
• is_prime: $0 \le x \le n$
• smallest_prime_factor: $2 \le x \le n$
• factorize, divisors: $1 \le x \le n$

計算量

• sieve(n): $\mathcal{O}(n)$
• is_prime, smallest_prime_factor, primes: $\mathcal{O}(1)$
• factorize: $\mathcal{O}(\log x)$
• divisors: $\mathcal{O}(d(x) \log d(x))$

Verified with

• test/aoj/NTL_1_A.test.cpp
• test/library-checker/enumerate_primes.test.cpp
• test/unit/sieve.test.cpp

Code

#pragma once
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
struct sieve {
public:
    sieve() : sieve(1) {
    }
    explicit sieve(int n) : _n(n), lpf(n + 1, 0) {
        assert(n >= 1);
        for (int i = 2; i <= n; i++) {
            if (lpf[i] == 0) {
                lpf[i] = i;
                _primes.push_back(i);
            }
            for (int p : _primes) {
                if (p > lpf[i] || (long long)p * i > n) break;
                lpf[p * i] = p;
            }
        }
    }
    bool is_prime(int x) const {
        assert(0 <= x && x <= _n);
        return x >= 2 && lpf[x] == x;
    }
    int smallest_prime_factor(int x) const {
        assert(2 <= x && x <= _n);
        return lpf[x];
    }
    const std::vector<int>& primes() const {
        return _primes;
    }
    std::vector<std::pair<int, int>> factorize(int x) const {
        assert(1 <= x && x <= _n);
        std::vector<std::pair<int, int>> ret;
        while (x > 1) {
            int p = lpf[x];
            if (!ret.empty() && ret.back().first == p) {
                ret.back().second++;
            } else {
                ret.emplace_back(p, 1);
            }
            x /= p;
        }
        return ret;
    }
    std::vector<int> divisors(int x) const {
        assert(1 <= x && x <= _n);
        std::vector<int> ret = {1};
        for (auto [p, e] : factorize(x)) {
            int sz = int(ret.size());
            int q = 1;
            for (int i = 0; i < e; i++) {
                q *= p;
                for (int j = 0; j < sz; j++) ret.push_back(ret[j] * q);
            }
        }
        std::sort(ret.begin(), ret.end());
        return ret;
    }

private:
    int _n;
    std::vector<int> lpf, _primes;
};

#line 2 "math/sieve.hpp"
#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>
struct sieve {
public:
    sieve() : sieve(1) {
    }
    explicit sieve(int n) : _n(n), lpf(n + 1, 0) {
        assert(n >= 1);
        for (int i = 2; i <= n; i++) {
            if (lpf[i] == 0) {
                lpf[i] = i;
                _primes.push_back(i);
            }
            for (int p : _primes) {
                if (p > lpf[i] || (long long)p * i > n) break;
                lpf[p * i] = p;
            }
        }
    }
    bool is_prime(int x) const {
        assert(0 <= x && x <= _n);
        return x >= 2 && lpf[x] == x;
    }
    int smallest_prime_factor(int x) const {
        assert(2 <= x && x <= _n);
        return lpf[x];
    }
    const std::vector<int>& primes() const {
        return _primes;
    }
    std::vector<std::pair<int, int>> factorize(int x) const {
        assert(1 <= x && x <= _n);
        std::vector<std::pair<int, int>> ret;
        while (x > 1) {
            int p = lpf[x];
            if (!ret.empty() && ret.back().first == p) {
                ret.back().second++;
            } else {
                ret.emplace_back(p, 1);
            }
            x /= p;
        }
        return ret;
    }
    std::vector<int> divisors(int x) const {
        assert(1 <= x && x <= _n);
        std::vector<int> ret = {1};
        for (auto [p, e] : factorize(x)) {
            int sz = int(ret.size());
            int q = 1;
            for (int i = 0; i < e; i++) {
                q *= p;
                for (int j = 0; j < sz; j++) ret.push_back(ret[j] * q);
            }
        }
        std::sort(ret.begin(), ret.end());
        return ret;
    }

private:
    int _n;
    std::vector<int> lpf, _primes;
};

Back to top page