prime sieve
(include/emthrm/math/prime_sieve.hpp)

• View this file on GitHub
• Last update: 2023-02-23 21:59:12+09:00
• Include: #include "emthrm/math/prime_sieve.hpp"

時間計算量

$O(N)$

仕様

名前	戻り値
template <bool GETS_ONLY_PRIME> std::vector<int> prime_sieve(const int n);	$n$ 以下の素数または $i$ ($i \leq n$) の最小素因数

参考文献

• https://37zigen.com/linear-sieve/
• https://imulan.hatenablog.jp/entry/2019/09/29/212808

TODO

• $n$ 以下の素数の個数
  • http://sugarknri.hatenablog.com/entry/2019/07/31/102422
  • https://rsk0315.hatenablog.com/entry/2021/05/18/015511
  • https://rsk0315.github.io/slides/prime-counting.pdf
  • https://suu-0313.hatenablog.com/entry/2021/09/14/225759
  • https://sotanishy.github.io/cp-library-cpp/math/prime_count.hpp
  • https://judge.yosupo.jp/problem/counting_primes

Submissons

https://yukicoder.me/submissions/623330

Required by

• カーマイケル関数 (Carmichael function) の数表 (include/emthrm/math/carmichael_function_init.hpp)
• $i^k \bmod m$ ($0 \leq i \leq n$) (include/emthrm/math/enumerate_k-th_power.hpp)
• オイラーの $\varphi$ 関数 (Euler's totient function) の数表2 (include/emthrm/math/euler_phi_init2.hpp)
• メビウス関数 (Möbius function) の数表2 (include/emthrm/math/mobius_mu_init2.hpp)
• osa_k 法 (include/emthrm/math/osa_k.hpp)

Verified with

• 数学/$i^k \bmod m$ ($0 \leq i \leq n$) (test/math/enumerate_k-th_power.test.cpp)
• 数学/オイラーの $\varphi$ 関数/オイラーの $\varphi$ 関数の数表2 (test/math/euler_phi_init2.test.cpp)
• 数学/メビウス関数/メビウス関数の数表2 (test/math/mobius_mu_init2.test.cpp)
• 数学/osa_k 法 (test/math/osa_k.test.cpp)
• 数学/prime sieve (test/math/prime_sieve.test.cpp)

Code

#ifndef EMTHRM_MATH_PRIME_SIEVE_HPP_
#define EMTHRM_MATH_PRIME_SIEVE_HPP_

#include <numeric>
#include <vector>

namespace emthrm {

template <bool GETS_ONLY_PRIME>
std::vector<int> prime_sieve(const int n) {
  std::vector<int> smallest_prime_factor(n + 1), prime;
  std::iota(smallest_prime_factor.begin(), smallest_prime_factor.end(), 0);
  for (int i = 2; i <= n; ++i) {
    if (smallest_prime_factor[i] == i) [[unlikely]] prime.emplace_back(i);
    for (const int p : prime) {
      if (i * p > n || p > smallest_prime_factor[i]) break;
      smallest_prime_factor[i * p] = p;
    }
  }
  return GETS_ONLY_PRIME ? prime : smallest_prime_factor;
}

}  // namespace emthrm

#endif  // EMTHRM_MATH_PRIME_SIEVE_HPP_

#line 1 "include/emthrm/math/prime_sieve.hpp"



#include <numeric>
#include <vector>

namespace emthrm {

template <bool GETS_ONLY_PRIME>
std::vector<int> prime_sieve(const int n) {
  std::vector<int> smallest_prime_factor(n + 1), prime;
  std::iota(smallest_prime_factor.begin(), smallest_prime_factor.end(), 0);
  for (int i = 2; i <= n; ++i) {
    if (smallest_prime_factor[i] == i) [[unlikely]] prime.emplace_back(i);
    for (const int p : prime) {
      if (i * p > n || p > smallest_prime_factor[i]) break;
      smallest_prime_factor[i * p] = p;
    }
  }
  return GETS_ONLY_PRIME ? prime : smallest_prime_factor;
}

}  // namespace emthrm

Back to top page