n只会被最小质因子筛去。

O(n)

const int N=1000010;

int primes[N],res;
bool st[N];

void get_primes(int n)
{
    // LOOP1
    for(int i=2;i<=n;++i)
    {
        if(!st[i]) primes[res++]=i;
        // LOOP2
        for(int j=0;primes[j]<=n/i;++j)
        {
            st[primes[j]*i] = true;
            if(i%primes[j]==0) break;
        }
    }
}

为了更形象地体现线性筛的线性特点，列表。（初学到时不是很理解，怎么做到线性复杂度的。。）

根据表中的规律，可以发现线性筛法的特点 —— n只会被最小质因子筛去。

在检验过程中，

只要LOOP1的索引i可以被当前素数除尽时，即i%primes[j]==0，将不再继续LOOP2。因此LOOP2中使用的素数总是不会超过LOOP1的索引i：i%primes[j]==0，因为当前记录的最大素数即为i，对自身取余为0。

以上约束，保证了只会出现2x6而不会出现3x4这样的组合筛去12。以及不会出现3x2这种组合情况筛去6。