ACM算法竞赛——线性筛（模板）

线性筛时间复杂度O(n) 埃氏筛时间复杂度O(nloglogn)
埃氏筛会多次筛除一个元素，线性筛一个数只会被最小的质因数筛除

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;	//prime[j]一定是i的最小质因子
        }
    }
}