算法分析

• 朴素埃氏筛法o(nlogn)
  依次枚举从2~n的每个数，如果它没有被标记就说明它不能被任意的素数整除所以它就是是素数，那么把它的倍数全部标记一下。

for(int i = 2; i <= n; i ++)
{
    if(st[i]) continue;
    for(int j = i; j <= n; j += i)
        st[j] = true;
}

• 优化版埃氏筛法O(nloglogn)
  对于每个数假如它是素数x那么按照上述的算法描述小于x的倍数都会被标记，因此防止重复遍历，就应该从x^2开始标记。

for(int i = 2; i <= n; i ++)
{
    if(st[i])continue;
    for(int j = i; j <= n / i; j ++)st[i * j] = true;
}

• 线性筛法O(N)
  对于上述算法 假如 x = 12 那么 就会在i = 2的时候标记一次， i = 3标记一次 , 是因为没有从根本上找到唯一产生数x的原因。根据算术基本定理 可以得知，每个合数都能分解成一系列素数的乘机，那么我们只用每个合数的最小质因数标记不就行了吗。

for(int i = 2; i <= n; i ++)
{
    if(!st[i])primes[cnt ++] = i; // 没有被标记代表是素数
    for(int j = 0; primes[j] <= n / i; j ++) //不用j < cnt 来判断，是因为当i为素数的话枚举到i就会停止，当i为合数那么枚举到i的最小质因子也会停止
    {
        int pj = primes[j];
        st[pj * i] = true;//当i % pj != 0时 那么i就是i * pj的最小质因子，因为是从小到大枚举的质数。
        if(i % pj == 0)break;//当i % pj == 0 那么pj也是i * pj 的最小质因子。
    }
}

为什么每个合数都会被筛掉 假设一个x为合数那么必然存在 一个最小质因子 pj 当i枚举到x/pj的时候x就会被筛去，因为i枚举到x.pj的时候 x.pj前面的所有质数已经被处理出来了