Sieve of Eratosthenes
(math/number-theory/SieveofEratosthenes.hpp)

• View this file on GitHub
• Last update: 2025-05-20 01:52:42+09:00
• Include: #include "math/number-theory/SieveofEratosthenes.hpp"

概要

todo

計算量

todo

Code

vector<bool> prime_table(int n) {
  vector<bool> prime(n + 1, true);
  prime[0] = false;
  if (n >= 1) prime[1] = false;
  for (int i = 2; i * i <= n; i++) {
    if (!prime[i]) continue;
    for (int j = i * i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}

#line 1 "math/number-theory/SieveofEratosthenes.hpp"
vector<bool> prime_table(int n) {
  vector<bool> prime(n + 1, true);
  prime[0] = false;
  if (n >= 1) prime[1] = false;
  for (int i = 2; i * i <= n; i++) {
    if (!prime[i]) continue;
    for (int j = i * i; j <= n; j += i) {
      prime[j] = false;
    }
  }
  return prime;
}

Back to top page