This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#include "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)); } };
#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)); } };