完全理解线性筛 · znzryb
## 线性筛
线性筛的作用就是为了保证每个合数都只被其【最小的】那个质因数标记一次。
这下面👇讲的比较一般啊。
线性筛只有可能标记一个数字一次。
这个讲的有点复杂了，最后是关键，就是每个数只会以唯一方式被标记。
$$
m=\frac{n}{p_1}=p_{1}^{m_1-1}\times p_{2}^{m_2}\times p_{3}^{m_3} \times \cdots \times p_{k}^{m_k}
$$
n 只会在遍历到 m 时被标记。
假设这个n，在遍历到 m 之前就被标记，假设该数字是 m‘，但是 $m’\times \text{minp}[m']=n$ 是必须满足的条件，`if(p==minp[i]) break;` ，m‘ 只会标记到这个最小素因子*自身，因此 m’ 想标记 n，当且仅当 $m’\times \text{minp}[m']=n$。显然，m‘=m，得证。
[https://qoj.ac/submission/995868](https://qoj.ac/submission/995868)
[https://cp-algorithms.com/algebra/prime-sieve-linear.html](https://cp-algorithms.com/algebra/prime-sieve-linear.html)
```cpp
// minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
vector<ll> minp,primes;
void sieve(ll n){
minp.assign(n+5,0);
// minp[1]=1; // 加了这句话可能把 1 误判成素数，要小心
for(int i=2;i<=n;++i){
if(minp[i]==0){ // 是素数
minp[i]=i;
primes.push_back(i);
}
for(auto p:primes){
if(i*p>n){ // 超范围了
break;
}
minp[i*p]=p;
// 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
// i * p_next = (p * k) * p_next 最小的应该是p
if(p==minp[i]){
break;
}
}
}
}
```
使用线性筛的minp分解素因数更快，效率更高。
```cpp
vector<ll> prs;
for(int j=W[i];j>1;j/=minp[j]){ // 素因数分解
ll p=minp[j];
prs.pb(p);
}
sort(all(prs));
prs.resize(unique(all(prs))-prs.begin());
```