筛质数(欧拉筛)

分朴素版、埃氏筛法、线性筛法。

朴素版

朴素版介绍

就是从2到最后去掉每个数的倍数。

朴素版源码

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
        }

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

埃氏筛法

埃氏筛法介绍

属于朴素的优化，我们这时候只要筛除质数的倍数就行了，因为合数能分解质因数，而质数只有1和本身。

埃氏筛法源码

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
            for (int j = i + i; j <= n; j += i ) st[j] = true; 
        }

    }
}

线性筛法

线性筛法讲解

线性筛法在数量级为1e7的级别时候比埃氏筛法快一倍左右。线性筛我还没看懂，这里给几个思路。

线性筛法源码

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;
        }

    }
}