完全理解线性筛

线性筛

线性筛的作用就是为了保证每个合数都只被其【最小的】那个质因数标记一次。

这下面👇讲的比较一般啊。

线性筛只有可能标记一个数字一次。

这个讲的有点复杂了，最后是关键，就是每个数只会以唯一方式被标记。

$$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://cp-algorithms.com/algebra/prime-sieve-linear.html

//  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分解素因数更快，效率更高。

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());