数论-筛素数

普通筛法

int get_primes(int n )
{
    for(int i = 2; i <= n ; i ++ )
    {
        if(!st[i])  //如果是质数
        {   primes[cnt ++] = i;
        }
        for(int j = i * 2 ; j <= n ; j += i)  st[j] = true;
        //不管当前i是合数还是质数，都用来筛掉后面它的倍数
    }
}

埃式筛法

int get_primes(int n )
{
    for(int i = 2; i <= n ; i ++ )
    {
        if(!st[i])  //如果是质数
        {   primes[cnt ++] = i;
            for(int j = i * 2 ; j <= n ; j += i)  st[j] = true;  
            //只用质数i筛掉它的倍数（合数），也可以筛掉所有合数
        }
    }
}

线性筛法

int 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 ++ ) 
//判断条件解释：我们用primes[j]筛掉合数primes[j] * i，只用筛掉小于n的合数就可以了
        {
            st[primes[j] * i] = true;   

            if(i % primes[j] == 0) break;   
        }
    }
}