素数筛法算法

素数定义：

素数是指在大于 1 的自然数中，除了 1 和它本身外，没有其他因数的数。换句话说，素数只有两个正因数：1 和它本身。

注意：0和1既不是质数也不是合数。

inline bool isprime(int x)
{
    for(int i=2;i<=x-1;++i)
    {
        if(x%i==0)return 0;
    return 1;
    }
}
int main()
{
    int N;
    scanf("%d",&N);
    for(int i=2;i<=N;++i)
        if(isprime(i))printf("%d",i);
    return 0;
}

这段带代码为了找出2--N以内的素数，所以在函数isprime函数内进行筛选，通过素数定义很容易理解这串代码，但是在时间上的优化还远远不够。

eg ：13

如果按照上面的代码，我们需要判断2——12。

inline bool isprime(int x)
{
    int sq=sqrt(x);
    for(int i=2;i<=sq&&i<sq;++i)
    {
        if(x%i==0)return 0;
    return 1;
    }
}

优化一下，将这个数开一下平方，缩小一下范围，虽然提高了运行速度，但还远远不够。

i<=sqrt（x）将两边平方：i*i<=x,但是如果i太大的话i*i就会溢出，改写一下变成i<=x/i,代码为：

inline bool isprime(int x)
{
    int sq=sqrt(x);
    for(int i=2;i<=x/i;++i)
    {
        if(x%i==0)return 0;
    return 1;
    }
}

朴素筛法

一个合数，一定存在非1非本身质因子，意思就是，例如合数4，它一定是2*2，当我们得到2时，把2的倍数都筛掉，留下来的就是素数。

const int maxn=1e6+18;
bitset<maxn> pri; //默认全为0
inline bool isprime(int x)
{
    for(int i=2;i<=x/i;++i)
        {
        if(x%i==0)return 0;
     return 1;   
        }
}

int main()
{
    int N=1e6,cnt=0;
    for(int i=2;i<=N;++i)
    {
        if(isprime(i))
            for(int j=2*i;j<=N;j+=1)pri[j]=1;
    }
        for(int i=2;i<=N;++i)if(!pri[i])cnt++;
}

这里就已经构成了筛法，但是思考一下可以发现，代码中可以不需要素数判断。

const int maxn=1e6+18;
bitset<maxn> pri; //默认全为0


int main()
{
    int N=1e6,cnt=0;
    for(int i=2;i<=N;++i)
    {
        if(！pri[i])
            for(int j=2*i;j<=N;j+=1)pri[j]=1;
    }
        for(int i=2;i<=N;++i)if(!pri[i])cnt++;
}

欧拉筛法

原理：欧拉筛法的核心思想是通过排除法，逐一标记合数，同时确保每个合数只被其最小的质因数标记一次。具体步骤如下：

const int maxn=1e7+10;
bistset<maxn> pri;0为素数，1为合数(被筛除)
int primes[maxn],pp=0;
int main()
{
    int N=1e7,cnt=0;
    for(int i=2;i<=N;++i)
    {
        if(!pri[i])primes[++pp]=i,cnt++;
        for(int j=1;primes[j]*i<=N;++j)
            {
                pri[primes[j]*i]=1;
                if(i%primes[j]==0)break;
            }
    }
}