线性筛素数
也叫欧拉筛。
int pr[maxn]; bool flg[maxn];
int main() {for (int i = 2; i < maxn; ++i) {if (!flg[i]) pr[++pr[0]] = i;for (int j = 1; i * pr[j] <= n && j <= pr[0]; ++j) {flg[i * pr[j]] = 1;if (i % pr[j] == 0) break; // 重点}}
}
这样筛的话，若合数 n = p 1 a 1 p 2 a 2 ⋯ p k a k n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} n=p1a1p2a2⋯pkak（ p 1 < p 2 < ⋯ < p k p_1 < p_2 < \cdots < p_k p1<p2<⋯<pk），则 n n n 会在 i = n p 1 , p r [ j ] = p 1 i = \frac{n}{p_1}, pr[j] = p_1 i=p1n,pr[j]=p1 处被筛去，也只会在这里被筛去。也就是说，每个数都会被它最小的质因子筛去。if(i%pr[j]==0)break; 这句话保证了复杂度。
将合数分解为 n = p ∗ i n = p*i n=p∗i（ p p p 是 n n n 最小的质因子），
相当于 n = p ∗ ( p 1 a 1 − 1 p 2 a 2 ⋯ p k a k ) n=p*(p_1^{a_1-1} p_2^{a_2} \cdots p_k^{a_k}) n=p∗(p1a1−1p2a2⋯pkak)， i = p 1 a 1 − 1 p 2 a 2 ⋯ p k a k i=p_1^{a_1-1} p_2^{a_2} \cdots p_k^{a_k} i=p1a1−1p2a2⋯pkak
如果 p ∤ i p \nmid i p∤i，则构造合数n被筛掉
如果 p ∣ i p \mid i p∣i ，表示 p = p 1 p = p_1 p=p1，是 i i i 的最小质因子，需要构造n后停止循环。
- 如果继续用质数表中大于 p 1 p_1 p1 的后面的质数 p j p_{j} pj 构造 n j n_j nj（ j > 1 j>1 j>1）
设当前 i j = p 1 a 1 p 2 a 2 ⋯ p j a j − 1 ⋯ p k a k i_j=p_1^{a_1} p_2^{a_2} \cdots p_{j}^{a_{j}-1} \cdots p_k^{a_k} ij=p1a1p2a2⋯pjaj−1⋯pkak，则 n j = p j ∗ i j = p 1 a 1 p 2 a 2 ⋯ p j a j ⋯ p k a k n_j = p_j*i_j = p_1^{a_1} p_2^{a_2} \cdots p_{j}^{a_{j}} \cdots p_k^{a_k} nj=pj∗ij=p1a1p2a2⋯pjaj⋯pkak， - 之后当 i x = p 1 a 1 p 2 a 2 ⋯ p x a x − 1 ⋯ p k a k i_x=p_1^{a_1} p_2^{a_2} \cdots p_{x}^{a_x-1} \cdots p_k^{a_k} ix=p1a1p2a2⋯pxax−1⋯pkak（ x < j x<j x<j， i x > i j i_x>i_j ix>ij），与 p x p_x px构造合数 n x n_x nx， n x = p x ∗ i x = p 1 a 1 p 2 a 2 ⋯ p k a k = n j n_x=p_{x}*i_x= p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k} = n_j nx=px∗ix=p1a1p2a2⋯pkak=nj。故需提前break
- 直观点看，i小 * p大 == i大 * p小的数（i大会在i小之后出现）
例如
i=6=2 * 3 * 3 18
i = 9 = 3 * 3 * 2 18
具体的严谨证明详见初等数论的容斥原理
