数论进阶指南

数论

线性筛

复杂度:$O(n)$

A. 线性筛素数

自己对线性筛素数这东西其实一直很困惑，毕竟不理解为什么加了

if(i%pri[j]==0) break;

这一句之后，就可以保证每个数只被最小质因子筛去了。今天就开始补坑！

证明：一个数i当它找到它的最小质因子pri[j]时（因为pri数组中质数从小到大）,分为两种情况:

a. i为合数，我们不妨设$i=pri[j]*x$,
如果继续筛的话，我们其实是把$N=i*pri[j+1]$筛去，
那么可以写作$N=x*pri[j]*pri[j+1]$，
此时N应当在$i=pri[j+1]*x$时被$pri[j]$筛去，才满足被最小质因子筛去。
同理对于$pri[j+2],pri[j+3]....$

b. i为质数，此时我们一定是遍历到i本身，即$pri[j]==i$,我们之后就没有素数了，$break$即可

B.线性筛欧拉函数