Sieve of Eratosthenes (using bitset)
(number-theory/bitset_sieve.hpp)

• View this file on GitHub
• Last update: 2023-07-25 00:50:50+07:00
• Include: #include "number-theory/bitset_sieve.hpp"

Verified with

• number-theory/test/Enumerate_Primes.test.cpp

Code

template <int LIMN>
struct bitset_sieve {
  vector<int> primes;
  bitset<LIMN + 1> is_prime;
  const int maxN;
  bitset_sieve(int MAXN = LIMN) : maxN(MAXN) {
    is_prime.set();
    is_prime.reset(0), is_prime.reset(1);
    for (int p = 2; p <= MAXN; p++) {
      if (is_prime[p]) {
        primes.push_back(p);
        for (int j = p * 2; j <= MAXN; j += p) is_prime[j] = 0;
      }
    }
  }
  // Count primes less than or equal to x
  int prime_counting(int x) {
    assert(x <= maxN);
    return distance(primes.begin(),
                    upper_bound(primes.begin(), primes.end(), x));
  }
};

#line 1 "number-theory/bitset_sieve.hpp"
template <int LIMN>
struct bitset_sieve {
  vector<int> primes;
  bitset<LIMN + 1> is_prime;
  const int maxN;
  bitset_sieve(int MAXN = LIMN) : maxN(MAXN) {
    is_prime.set();
    is_prime.reset(0), is_prime.reset(1);
    for (int p = 2; p <= MAXN; p++) {
      if (is_prime[p]) {
        primes.push_back(p);
        for (int j = p * 2; j <= MAXN; j += p) is_prime[j] = 0;
      }
    }
  }
  // Count primes less than or equal to x
  int prime_counting(int x) {
    assert(x <= maxN);
    return distance(primes.begin(),
                    upper_bound(primes.begin(), primes.end(), x));
  }
};

Back to top page