WIKI

筛

欧拉筛

$$ \begin{align} x&=p_1^{\alpha_{1}}p_2^{\alpha_{2}}p_3^{\alpha_{3}}\dots\\ x&=ij\qquad j\in primes \qquad &j\in[&p_1,p_2,p_3\dots]\\ &&i \in [&p_1^{\alpha_{1}-1}p_2^{\alpha_{2}}p_3^{\alpha_{3}},\\&&&p_1^{\alpha_{1}}p_2^{\alpha_{2-1}}p_3^{\alpha_{3}},\\&& \qquad &p_1^{\alpha_{1}}p_2^{\alpha_{2}}p_3^{\alpha_{3-1}}\dots]\\ &形如p_1^{\alpha_{1}}p_2^{\alpha_{2-1}}p_3^{\alpha_{3}},p_1^{\alpha_{1}}p_2^{\alpha_{2}}p_3^{\alpha_{3-1}}会被 p_1筛掉\\ &时间复杂度可以保证在O(n) \end{align} $$

code

constexpr int N = 1E7 + 10;
bool not_prime[N];
int prime[N], tot = 0;
for (int i = 2; i <= n; i++) {
  if (!not_prime[i]) prime[++tot] = i;
  for (int j = 1; j <= tot and i * prime[j] <= n; j++) {
    not_prime[i * prime[j]] = 1;
    if (i % prime[j] == 0) break;
  }
}