素数篩
(number-theory/prime-sieve.hpp)

• View this file on GitHub
• Last update: 2026-07-25 02:01:37+09:00
• Include: #include "number-theory/prime-sieve.hpp"

素数篩

$0$ 以上 $N$ 以下の整数を篩により処理する．

• PrimeSieve::lpf(N)：lpf[x] が $x$ の最小素因数となる長さ $N+1$ の列を返す．ただし，lpf[0] = 0，lpf[1] = 1 とする．
• PrimeSieve::table(N)：$N$ 以下の素数を昇順に並べた列を返す．
• PrimeSieve::factorize(N)：factors[x] が $x$ の素因数と指数の組を昇順に並べた列となる，長さ $N+1$ の列を返す．$0$ と $1$ に対応する列は空である．

時間計算量は $O(N\log\log N)$．

Required by

• 有名数列 (fps/famous-sequences.hpp)
• Power Table (modint/power-table.hpp)
• Count Square Free (number-theory/count-square-free.hpp)
• Lucy DP (number-theory/lucy-dp.hpp)
• Mobius Function (number-theory/mobius-function.hpp)
• 素数の剰余類別集計 (number-theory/prime-residue.hpp)
• 区間篩 (number-theory/range-sieve.hpp)
• number-theory/sum-of-multiplicative-function.hpp
• Totient Function (number-theory/totient-function.hpp)

Verified with

• verify/fps/LC_bell_number.test.cpp
• verify/fps/LC_montmort_number_mod.test.cpp
• verify/fps/LC_partition_function.test.cpp
• verify/fps/LC_stirling_number_of_the_first_kind.test.cpp
• verify/fps/LC_stirling_number_of_the_first_kind_fixed_k.test.cpp
• verify/fps/LC_stirling_number_of_the_second_kind.test.cpp
• verify/fps/LC_stirling_number_of_the_second_kind_fixed_k.test.cpp
• verify/fps/LC_sum_of_exponential_times_polynomial.test.cpp
• verify/fps/LC_sum_of_exponential_times_polynomial_limit.test.cpp
• verify/number-theory/LC_counting_squarefrees.test.cpp
• verify/number-theory/LC_enumerate_primes.test.cpp
• verify/number-theory/LC_sum_of_multiplicative_function.test.cpp
• verify/number-theory/LC_sum_of_totient_function.test.cpp
• verify/number-theory/UNIT_mobius_function.test.cpp
• verify/number-theory/UNIT_prime_residue.test.cpp
• verify/number-theory/UNIT_prime_sieve.test.cpp
• verify/number-theory/UNIT_range_sieve_table.test.cpp

Code

#pragma once

namespace PrimeSieve {
using ll = long long;

vector<int> lpf(int n) {
  assert(n >= 0);
  vector<int> ret(n + 1);
  for (size_t i = 0; i < ret.size(); i++) ret[i] = (int)i;
  for (int p = 2; (ll)p * p <= n; p++) {
    if (ret[p] != p) continue;
    for (ll x = (ll)p * p;; x += p) {
      if (ret[x] == x) ret[x] = p;
      if (n - x < p) break;
    }
  }
  return ret;
}

vector<int> table(int n) {
  assert(n >= 0);
  vector<bool> composite(n + 1, false);
  for (int p = 2; (ll)p * p <= n; p += (p & 1) + 1) {
    if (composite[p]) continue;
    for (ll x = (ll)p * p;; x += p) {
      composite[x] = true;
      if (n - x < p) break;
    }
  }
  vector<int> ps;
  for (int p = 2; p <= n;) {
    if (!composite[p]) ps.push_back(p);
    int step = (p & 1) + 1;
    if (n - p < step) break;
    p += step;
  }
  return ps;
}

vector<vector<pair<ll, int>>> factorize(int n) {
  assert(n >= 0);
  vector<vector<pair<ll, int>>> factors(n + 1);
  auto lp = lpf(n);
  for (int x = 2; x <= n;) {
    int y = x;
    while (y > 1) {
      int p = lp[y], e = 0;
      while (y % p == 0) y /= p, e++;
      factors[x].emplace_back(p, e);
    }
    if (x == n) break;
    x++;
  }
  return factors;
}
};  // namespace PrimeSieve

/**
 * @brief 素数篩
 * @docs docs/number-theory/prime-sieve.md
 */

#line 2 "number-theory/prime-sieve.hpp"

namespace PrimeSieve {
using ll = long long;

vector<int> lpf(int n) {
  assert(n >= 0);
  vector<int> ret(n + 1);
  for (size_t i = 0; i < ret.size(); i++) ret[i] = (int)i;
  for (int p = 2; (ll)p * p <= n; p++) {
    if (ret[p] != p) continue;
    for (ll x = (ll)p * p;; x += p) {
      if (ret[x] == x) ret[x] = p;
      if (n - x < p) break;
    }
  }
  return ret;
}

vector<int> table(int n) {
  assert(n >= 0);
  vector<bool> composite(n + 1, false);
  for (int p = 2; (ll)p * p <= n; p += (p & 1) + 1) {
    if (composite[p]) continue;
    for (ll x = (ll)p * p;; x += p) {
      composite[x] = true;
      if (n - x < p) break;
    }
  }
  vector<int> ps;
  for (int p = 2; p <= n;) {
    if (!composite[p]) ps.push_back(p);
    int step = (p & 1) + 1;
    if (n - p < step) break;
    p += step;
  }
  return ps;
}

vector<vector<pair<ll, int>>> factorize(int n) {
  assert(n >= 0);
  vector<vector<pair<ll, int>>> factors(n + 1);
  auto lp = lpf(n);
  for (int x = 2; x <= n;) {
    int y = x;
    while (y > 1) {
      int p = lp[y], e = 0;
      while (y % p == 0) y /= p, e++;
      factors[x].emplace_back(p, e);
    }
    if (x == n) break;
    x++;
  }
  return factors;
}
};  // namespace PrimeSieve

/**
 * @brief 素数篩
 * @docs docs/number-theory/prime-sieve.md
 */

Back to top page