Sieve of Eratosthenes（エラトステネスの篩）
(algorithm/Math/NumberTheory/sieve.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Math/NumberTheory/sieve.hpp"

概要

$N$ 未満の自然数の中からすべての素数を発見する．

アルゴリズムの計算量は $\mathcal{O}(N \log \log N)$ となる．

本実装では，各自然数に対して最小の素因数 (LPF: Least Prime Factor) を求めており，「素数判定」に加え「高速素因数分解」などができる．

参考文献

1. “エラトステネスの篩”. Wikipedia. https://ja.wikipedia.org/wiki/エラトステネスの篩.
2. rsk0315_h4x. “エラトステネスの篩に基づく高速な素因数分解”. Qiita. https://qiita.com/rsk0315_h4x/items/ff3b542a4468679fb409.
3. drken. “エラトステネスの篩の活用法を総特集！ 〜 高速素因数分解・メビウスの反転公式 〜”. Qiita. https://qiita.com/drken/items/3beb679e54266f20ab63.
4. rsk0315. “素因数分解を <O(n), O(log(n)/log(log(n)))> で行う”. HatenaBlog. https://rsk0315.hatenablog.com/entry/2023/05/03/133029.

Verified with

• verify/aoj-ALDS1_1_C-sieve.test.cpp

Code

#ifndef ALGORITHM_SIEVE_HPP
#define ALGORITHM_SIEVE_HPP 1

#include <algorithm>
#include <cassert>
#include <map>
#include <numeric>
#include <vector>

namespace algorithm {

// Sieve of Eratosthenes（エラトステネスの篩）.
class Sieve {
    int m_sz;
    // m_lpf[i]:=(正の奇数2*i+1の最小素因数). Least prime factor. m_lpf[i]==2*i+1 のとき，2*i+1は素数．
    std::vector<int> m_lpf;

public:
    // constructor. n未満の自然数を篩にかける．O(N*loglogN).
    Sieve() : Sieve(0) {}
    explicit Sieve(int n) : m_sz(n), m_lpf(n / 2, -1) {
        assert(n >= 0);
        for(long long p = 3; p < m_sz; p += 2) {
            if(m_lpf[p / 2] == -1) {
                m_lpf[p / 2] = p;
                for(long long q = p * p; q < m_sz; q += 2 * p) {
                    if(m_lpf[q / 2] == -1) m_lpf[q / 2] = p;
                }
            }
        }
    }

    int size() const { return m_sz; }
    // 素数判定．O(1).
    bool is_prime(int n) const {
        assert(0 <= n and n < size());
        if(n == 2) return true;
        if(n % 2 == 0) return false;
        return m_lpf[n / 2] == n;
    }
    // 自然数nの最小素因数を取得する．O(1).
    int lpf(int n) const {
        assert(0 <= n and n < size());
        if(n < 2) return -1;
        if(n % 2 == 0) return 2;
        return m_lpf[n / 2];
    }
    // 高速素因数分解．O(logN).
    std::map<int, int> prime_factorize(int n) const {
        assert(1 <= n and n < size());
        std::map<int, int> res;
        for(; n % 2 == 0; n /= 2) ++res[2];
        for(; n > 1; n /= m_lpf[n / 2]) ++res[m_lpf[n / 2]];
        return res;
    }
    // オイラーのファイ関数．n以下でnと互いに素な自然数の個数を求める．O(logN).
    int totient(int n) const {
        assert(1 <= n and n < size());
        int res = n;
        for(const auto &[p, _] : prime_factorize(n)) res -= res / p;
        return res;
    }
    // メビウス関数．O(N*loglogN).
    std::vector<int> mobius() const {
        std::vector<int> res(m_sz, 1);  // res[n]:=μ(n).
        for(int p = 2; p < m_sz; ++p) {
            if(lpf(p) == p) {
                res[p] = -1;
                for(int q = 2 * p; q < m_sz; q += p) {
                    if((q / p) % p == 0) res[q] = 0;  // nがある素数pで2回以上割り切れるとき，μ(n)=0.
                    else res[q] = -res[q];            // nがk個の相異なる素因数で分解できるとき，μ(n)=(-1)^k.
                }
            }
        }
        return res;
    }
};

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/NumberTheory/sieve.hpp"



#include <algorithm>
#include <cassert>
#include <map>
#include <numeric>
#include <vector>

namespace algorithm {

// Sieve of Eratosthenes（エラトステネスの篩）.
class Sieve {
    int m_sz;
    // m_lpf[i]:=(正の奇数2*i+1の最小素因数). Least prime factor. m_lpf[i]==2*i+1 のとき，2*i+1は素数．
    std::vector<int> m_lpf;

public:
    // constructor. n未満の自然数を篩にかける．O(N*loglogN).
    Sieve() : Sieve(0) {}
    explicit Sieve(int n) : m_sz(n), m_lpf(n / 2, -1) {
        assert(n >= 0);
        for(long long p = 3; p < m_sz; p += 2) {
            if(m_lpf[p / 2] == -1) {
                m_lpf[p / 2] = p;
                for(long long q = p * p; q < m_sz; q += 2 * p) {
                    if(m_lpf[q / 2] == -1) m_lpf[q / 2] = p;
                }
            }
        }
    }

    int size() const { return m_sz; }
    // 素数判定．O(1).
    bool is_prime(int n) const {
        assert(0 <= n and n < size());
        if(n == 2) return true;
        if(n % 2 == 0) return false;
        return m_lpf[n / 2] == n;
    }
    // 自然数nの最小素因数を取得する．O(1).
    int lpf(int n) const {
        assert(0 <= n and n < size());
        if(n < 2) return -1;
        if(n % 2 == 0) return 2;
        return m_lpf[n / 2];
    }
    // 高速素因数分解．O(logN).
    std::map<int, int> prime_factorize(int n) const {
        assert(1 <= n and n < size());
        std::map<int, int> res;
        for(; n % 2 == 0; n /= 2) ++res[2];
        for(; n > 1; n /= m_lpf[n / 2]) ++res[m_lpf[n / 2]];
        return res;
    }
    // オイラーのファイ関数．n以下でnと互いに素な自然数の個数を求める．O(logN).
    int totient(int n) const {
        assert(1 <= n and n < size());
        int res = n;
        for(const auto &[p, _] : prime_factorize(n)) res -= res / p;
        return res;
    }
    // メビウス関数．O(N*loglogN).
    std::vector<int> mobius() const {
        std::vector<int> res(m_sz, 1);  // res[n]:=μ(n).
        for(int p = 2; p < m_sz; ++p) {
            if(lpf(p) == p) {
                res[p] = -1;
                for(int q = 2 * p; q < m_sz; q += p) {
                    if((q / p) % p == 0) res[q] = 0;  // nがある素数pで2回以上割り切れるとき，μ(n)=0.
                    else res[q] = -res[q];            // nがk個の相異なる素因数で分解できるとき，μ(n)=(-1)^k.
                }
            }
        }
        return res;
    }
};

}  // namespace algorithm

Back to top page