prime/prime-sieve.hpp

• View this file on GitHub
• Last update: 2020-12-05 08:35:39+09:00
• Include: #include "prime/prime-sieve.hpp"

Verified with

• verify/verify-unit-test/primality-test.test.cpp
• verify/verify-yosupo-math/yosupo-prime-enumerate-sieve.test.cpp

Code

#pragma once

// Prime -> {0, 0, 1, 1, 0, 1, 0, 1, ...}
vector<bool> prime_sieve(int N) {
  vector<bool> sieve(max(1, N) + 1, 1);
  sieve[0] = sieve[1] = false;
  for (int i = 2; i * i <= N; i++)
    if (sieve[i] == true)
      for (int j = i * i; j <= N; j += i) sieve[j] = false;
  return sieve;
}

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

// Prime -> {0, 0, 1, 1, 0, 1, 0, 1, ...}
vector<bool> prime_sieve(int N) {
  vector<bool> sieve(max(1, N) + 1, 1);
  sieve[0] = sieve[1] = false;
  for (int i = 2; i * i <= N; i++)
    if (sieve[i] == true)
      for (int j = i * i; j <= N; j += i) sieve[j] = false;
  return sieve;
}

Back to top page