prime.hpp

SECTIONMath INCLUDEnoya/prime.hpp

线性筛出素数、最小质因子、欧拉函数和 Möbius 函数；适合上界可预处理的批量数论查询。

\[ \displaystyle \varphi(n)=n\prod_{p\mid n}\left(1-\frac1p\right) \]

Complexity: Time: O(n) sieve build, O(log x) table factorization. Space: O(n).

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n) sieve build, O(log x) table factorization.
/// Space: O(n).

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace noya {

/// @brief Linear sieve with smallest prime factors, Euler phi, and Mobius
/// values.
struct prime_table {
  int n = 0;
  std::vector<int> ps;
  std::vector<int> mnp;
  std::vector<int> phi;
  std::vector<int> mu;

  prime_table() = default;
  explicit prime_table(int n_) { build(n_); }

  /// @brief Build tables for every integer in [0, n].
  void build(int n_) {
    assert(n_ >= 0);
    n = n_;
    ps.clear();
    mnp.assign(n + 1, 0);
    phi.assign(n + 1, 0);
    mu.assign(n + 1, 0);
    if (n >= 1) {
      phi[1] = 1;
      mu[1] = 1;
    }
    for (int x = 2; x <= n; x++) {
      if (mnp[x] == 0) {
        mnp[x] = x;
        phi[x] = x - 1;
        mu[x] = -1;
        ps.push_back(x);
      }
      for (int p : ps) {
        if (p > n / x) {
          break;
        }
        mnp[x * p] = p;
        if (x % p == 0) {
          phi[x * p] = phi[x] * p;
          mu[x * p] = 0;
          break;
        }
        phi[x * p] = phi[x] * (p - 1);
        mu[x * p] = -mu[x];
      }
    }
  }

  bool is_prime(int x) const {
    assert(0 <= x && x <= n);
    return x >= 2 && mnp[x] == x;
  }

  /// @brief Factor x in O(log x); x must lie in [1, n].
  std::vector<std::pair<int, int>> factorize(int x) const {
    assert(1 <= x && x <= n);
    std::vector<std::pair<int, int>> res;
    while (x > 1) {
      int p = mnp[x];
      int exp = 0;
      do {
        x /= p;
        exp++;
      } while (x % p == 0);
      res.emplace_back(p, exp);
    }
    return res;
  }

  /// @brief Enumerate the positive divisors of x in increasing order.
  std::vector<int> divisors(int x) const {
    std::vector<int> res = {1};
    for (auto [p, exp] : factorize(x)) {
      int os = int(res.size());
      int pw = 1;
      for (int e = 1; e <= exp; e++) {
        pw *= p;
        for (int i = 0; i < os; i++) {
          res.push_back(res[i] * pw);
        }
      }
    }
    std::sort(res.begin(), res.end());
    return res;
  }
};

} // namespace noya

#ifndef NOYA_PRIME_HPP
#define NOYA_PRIME_HPP 1

/// @complexity Time: O(n) sieve build, O(log x) table factorization.
/// Space: O(n).

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace noya {

/// @brief Linear sieve with smallest prime factors, Euler phi, and Mobius
/// values.
struct prime_table {
  int n = 0;
  std::vector<int> ps;
  std::vector<int> mnp;
  std::vector<int> phi;
  std::vector<int> mu;

  prime_table() = default;
  explicit prime_table(int n_) { build(n_); }

  /// @brief Build tables for every integer in [0, n].
  void build(int n_) {
    assert(n_ >= 0);
    n = n_;
    ps.clear();
    mnp.assign(n + 1, 0);
    phi.assign(n + 1, 0);
    mu.assign(n + 1, 0);
    if (n >= 1) {
      phi[1] = 1;
      mu[1] = 1;
    }
    for (int x = 2; x <= n; x++) {
      if (mnp[x] == 0) {
        mnp[x] = x;
        phi[x] = x - 1;
        mu[x] = -1;
        ps.push_back(x);
      }
      for (int p : ps) {
        if (p > n / x) {
          break;
        }
        mnp[x * p] = p;
        if (x % p == 0) {
          phi[x * p] = phi[x] * p;
          mu[x * p] = 0;
          break;
        }
        phi[x * p] = phi[x] * (p - 1);
        mu[x * p] = -mu[x];
      }
    }
  }

  bool is_prime(int x) const {
    assert(0 <= x && x <= n);
    return x >= 2 && mnp[x] == x;
  }

  /// @brief Factor x in O(log x); x must lie in [1, n].
  std::vector<std::pair<int, int>> factorize(int x) const {
    assert(1 <= x && x <= n);
    std::vector<std::pair<int, int>> res;
    while (x > 1) {
      int p = mnp[x];
      int exp = 0;
      do {
        x /= p;
        exp++;
      } while (x % p == 0);
      res.emplace_back(p, exp);
    }
    return res;
  }

  /// @brief Enumerate the positive divisors of x in increasing order.
  std::vector<int> divisors(int x) const {
    std::vector<int> res = {1};
    for (auto [p, exp] : factorize(x)) {
      int os = int(res.size());
      int pw = 1;
      for (int e = 1; e <= exp; e++) {
        pw *= p;
        for (int i = 0; i < os; i++) {
          res.push_back(res[i] * pw);
        }
      }
    }
    std::sort(res.begin(), res.end());
    return res;
  }
};

} // namespace noya

#endif // NOYA_PRIME_HPP

#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

/// @complexity Time: O(n) sieve build, O(log x) table factorization.
/// Space: O(n).

namespace noya {

/// @brief Linear sieve with smallest prime factors, Euler phi, and Mobius
/// values.
struct prime_table {
  int n = 0;
  std::vector<int> ps;
  std::vector<int> mnp;
  std::vector<int> phi;
  std::vector<int> mu;

  prime_table() = default;
  explicit prime_table(int n_) { build(n_); }

  /// @brief Build tables for every integer in [0, n].
  void build(int n_) {
    assert(n_ >= 0);
    n = n_;
    ps.clear();
    mnp.assign(n + 1, 0);
    phi.assign(n + 1, 0);
    mu.assign(n + 1, 0);
    if (n >= 1) {
      phi[1] = 1;
      mu[1] = 1;
    }
    for (int x = 2; x <= n; x++) {
      if (mnp[x] == 0) {
        mnp[x] = x;
        phi[x] = x - 1;
        mu[x] = -1;
        ps.push_back(x);
      }
      for (int p : ps) {
        if (p > n / x) {
          break;
        }
        mnp[x * p] = p;
        if (x % p == 0) {
          phi[x * p] = phi[x] * p;
          mu[x * p] = 0;
          break;
        }
        phi[x * p] = phi[x] * (p - 1);
        mu[x * p] = -mu[x];
      }
    }
  }

  bool is_prime(int x) const {
    assert(0 <= x && x <= n);
    return x >= 2 && mnp[x] == x;
  }

  /// @brief Factor x in O(log x); x must lie in [1, n].
  std::vector<std::pair<int, int>> factorize(int x) const {
    assert(1 <= x && x <= n);
    std::vector<std::pair<int, int>> res;
    while (x > 1) {
      int p = mnp[x];
      int exp = 0;
      do {
        x /= p;
        exp++;
      } while (x % p == 0);
      res.emplace_back(p, exp);
    }
    return res;
  }

  /// @brief Enumerate the positive divisors of x in increasing order.
  std::vector<int> divisors(int x) const {
    std::vector<int> res = {1};
    for (auto [p, exp] : factorize(x)) {
      int os = int(res.size());
      int pw = 1;
      for (int e = 1; e <= exp; e++) {
        pw *= p;
        for (int i = 0; i < os; i++) {
          res.push_back(res[i] * pw);
        }
      }
    }
    std::sort(res.begin(), res.end());
    return res;
  }
};

} // namespace noya