线性筛

思想：确保每个合数只被最小质因数筛掉。
例如：12=2*2*3，如果通过埃氏筛12会被2和3各筛一次，这就多了一次不必要的操作。但通过线性筛可以确保12只被2筛。
具体实现方法：对于一个质数p，我们所需要筛出的数为2p,3p,…,kp。因为我们每次是从小到大依次枚举，即2,3,…,n。
对比得，第二个数列是第一个数列的系数。所以我们不需要用一个for循环去筛除一个质数的所有倍数，我们将所有质数存储到primes数组中，然后枚举到第i个数时，就筛去所有的primes[j] * i。这样就在每一次遍历中，正好筛除了所有已知素数的i倍。
注意，当i%primes[j]==0, 我们就结束内层循环。
证明：
1 ：i%primes[j]==0 
2 ：primes[j]*k=i 
设：
3：primes[j+1]*i=X  将2式带入3中得：
primes[j+1]*primes[j]*k=X 
因为：primes[j+1]>primes[j] 
所以：primes[j+1]* k> i,设primes[j+1]* k=i′ 
则：4：primes[j]* i′=X  
所以如果用3式筛去x的话，当i等于i ′时,x又会被4式筛去一次，为了确保合数只被最小质因子筛掉，最小质因子要乘以最大的倍数，即要乘以最大的I,所以不能提前筛。
举例：n=12,当i=4时，prime={2,3},此时i%2==0,如果不结束内层循环，12就会被34筛掉，而当i==6时12又会被26筛掉。

void ola() 
{ 
    for (int i = 2; i <= n; i ++ ) 
    { 
        if (st[i] == 0) primes[cnt ++ ] = i;//将质数存到primes中 
        for (int j = 0; j<cnt&&i*primes[j] <= n; j ++ )//要确保质数的第i倍是小于等于n的。 
        {
             st[primes[j] * i] = 1; 
            if (i % primes[j] == 0) break; 
        }
    } 
}
例题