康复计划之线性筛

假如我给你一个n，让你输出n以内所有的素数，你会怎么做？

最好想的做法是一个一个枚举，然后检验，复杂度O(n*√n)

那有没有更优的做法呢？

理论上最低复杂度是n，那么能达到吗？

我们看下面一段代码：

inline void pre_() {
    for(int i=2;i<=n;i++) pp[i] = 1 ; pp[1] = 0 ;   // pp为bool型数组，记录数字i是否为素数，筛之前我们默认2以后都为素数
    for(int i=2;i<=n;i++) {
        if(pp[i]) prime[++tot] = i ;                 // 如果一个数是素数，就把他放到prime数组中
        for(int j=1;j<=tot&&prime[j]*i<=n;j++) {          
            pp[i*prime[j]] = 0 ;                      // 筛
            if(!(i%prime[j])) break ;                // 优化 达到线性目的的关键
        }
    }
}

为什么它是线性的呢？

我们只需要证明两点：

1，每个合数都会被筛掉

2，每个被筛掉的合数只会被筛一次

我们把每个合数分解为a1*a2*...*an的形式。（其中a1-an都是素数，a1<a2<...<an）

对于1：当i为a2*a3*...*an时，prime[j]为a1时，该数一定会被筛掉

对于2：当prime[j]=ax（x!=1), i=a1*...*ax-1*ax+1*...*an时，由于当prime[j]=a1时就会从循环中break出来，而a1 < ax, 所以无法令j满足prime[j]=ax，所以一个数不存在其他被筛的机会。

得证

于是我们就有了一个理论最低复杂度的筛素数方法啦！