线性筛

找到[1,n]之间的所有素数

互质 ：公约数只有1

质数：因子只有1和本身

1不是质数

线性筛：

1、任何合数都可以分成一个数a乘一个质数b

2、利用最大因数乘最小质数来筛

首先为啥可以线性的？

因为每次找的是最大因子和最小质数

如何保证筛一遍且每次保证只用最小的质因子把他筛掉？

i%p==0(p为质数）

假设t=i*p;   如果i%p==0,这说明如果你用再继续乘一个更大的质数，就会造成，这个i 不是最大因子，因为p更小啊

int p[maxn], pre[maxn],cnt;
int work(int maxn) {
for(int i=2; i<maxn; i++){
    if(!p[i]) {
            pre[cnt++]=i;
        }
        for(int j=0; j<cnt&&i*pre[j]<maxn; i++) {
            p[i*pre[j]]=1;
            if(i%pre[j]==0)break;
        }
    }
}