很多题解口头语言过于多,不是很好懂,且不够准确,y 总说的两种情况我认为应该对应我下面所说的两类式子,很多题解关于为什么最小质因子不能大于 $i$ 的最小质因子也未提及
在埃氏筛法中,一个数会被反复筛,这也是线性筛法的优化点
原则:每个数只被它的最小质因数筛掉
设枚举的 $i$ 值为 $p_1^{r_1}p_2^{p_2}…p_k^{r_k}$,最小质因子为 $p$
分为两种情况:
$p$ 是 $i$ 的最小质因子,筛掉的数 $n=p_1^{r_1+1}p_2^{p_2}…p_k^{r_k}$
$p$ 小于 $i$ 的所有质因子,筛掉的数 $n=p~p_1^{r_1}p_2^{p_2}…p_k^{r_k}$
那么 $p$ 显然是不能大于 $i$ 的最小质因子的,否则与 $p$ 的最小性矛盾
证明所有的合数一定可以按照上述的方式被筛掉,对于一个合数 $n$,$p$ 为其的最小质因子,则 $i$ 枚举到 $\frac{n}{p}$ 的时候会被筛掉