$数学知识之线性筛法$

$在埃氏筛法的基础上,考虑到有重复筛去元素这样的重复操作$

$例如6被2筛掉后,又被3重复筛掉,导致达不到线性$

$思考每一个合数,只要被一个素数筛去一次就够了,这时应该用最小的质因子去筛$

$当任意数i从小到大遍历比它小的所有质数时$

$第一次使得i \ mod\ j = 0 的数就是i的最小质因数$

$那么\forall 1 \leq x \leq j 的质数,x一定是 i \times x 的最小质因数,此时i \times x 就会被筛去$

$反之,x就一定不是它的最小值因数,那么就没有筛去的意义$

$Code$

void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!p[i])q[++tot] = i;
        for (int j = 1; q[j] <= n / i; j ++ )
        {
            p[i * q[j]] = true;
            if (i % q[j] == 0)break;
        }
    }
}