Description:
(NT/prime/sieve/bool_sieve.hpp)

• View this file on GitHub
• Last update: 2024-06-01 22:35:41+07:00
• Include: #include "NT/prime/sieve/bool_sieve.hpp"

Description:

Prime sieve that return bool useful when to check number is prime or not

Time:

• $O(Nloglog(N))$

Verified with

• test/yosupo/Math/enum_prime_5.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 "NT/prime/sieve/bool_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