素数篩
(math/prime-sieve.hpp)

• View this file on GitHub
• Last update: 2025-10-21 21:13:36+09:00
• Include: #include "math/prime-sieve.hpp"

Code

#pragma once

vector<int> PrimeSieve(int n) {
  vector<bool> f(n + 1, false);
  for (int p = 2; p * p <= n; p += (p & 1) + 1) {
    if (f[p]) continue;
    for (int i = p * p; i <= n; i += p) f[i] = true;
  }
  vector<int> ps;
  for (int p = 2; p <= n; p += (p & 1) + 1)
    if (!f[p]) ps.push_back(p);
  return ps;
}
/**
 * @brief 素数篩
 */

#line 2 "math/prime-sieve.hpp"

vector<int> PrimeSieve(int n) {
  vector<bool> f(n + 1, false);
  for (int p = 2; p * p <= n; p += (p & 1) + 1) {
    if (f[p]) continue;
    for (int i = p * p; i <= n; i += p) f[i] = true;
  }
  vector<int> ps;
  for (int p = 2; p <= n; p += (p & 1) + 1)
    if (!f[p]) ps.push_back(p);
  return ps;
}
/**
 * @brief 素数篩
 */

Back to top page