src/math/prime.hpp

• View this file on GitHub
• Last update: 2025-10-26 10:54:48+08:00
• Include: #include "src/math/prime.hpp"

Verified with

• test/math/prime.test.cpp

Code

vector<int> primes;
bitset<MAXN> isprime;
void init_prime_table() {
  isprime.set();
  isprime[0] = isprime[1] = false;
  for (int i = 2; i < MAXN; i++) {
    if (isprime[i]) primes.PUSHB(i);
    for (int p : primes) {
      if (i * p >= MAXN) break;
      isprime[i * p] = false;
      if (i % p == 0) break;
    }
  }
}

#line 1 "src/math/prime.hpp"
vector<int> primes;
bitset<MAXN> isprime;
void init_prime_table() {
  isprime.set();
  isprime[0] = isprime[1] = false;
  for (int i = 2; i < MAXN; i++) {
    if (isprime[i]) primes.PUSHB(i);
    for (int p : primes) {
      if (i * p >= MAXN) break;
      isprime[i * p] = false;
      if (i % p == 0) break;
    }
  }
}

Back to top page