素数

素数筛一般可以用做预处理。

1.素数筛选：判断小于maxn的数是不是素数

这个板子用于判断一个小于maxn的数是不是素数，打一个表存脚标是否为素数的情况。

#include<iostream>
#include<cstring>

using namespace std;
const int maxn = 1000010;
bool notprime[maxn];///值为false表示素数，值为true表示不是素数
void init()
{
    memset(notprime,false,sizeof(notprime));
    notprime[0] = notprime[1] = true;
    for(int i=2;i<maxn;i++)
    {
        if(!notprime[i])
        {
            if(i>maxn/i)
                continue;///防止i*i溢出
            for(int j=i*i;j<maxn;j+=i)
            {
                notprime[j] = true;
            }
        }
    }
}

int main()
{
    init();
    for(int i=0;i<1000;i++)
        cout<<i<<' '<<notprime[i]<<endl;
    return 0;
}

2.素数筛选，存在小于等于maxn的素数

计算的是素数的个数

#include<iostream>
#include<cstring>

using namespace std;
const int maxn = 1000010;
int prime[maxn+1];
void getPrime()
{
    memset(prime,0,sizeof(prime));
    for(int i=2;i<=maxn;i++)
    {
        if(!prime[i])
            prime[++prime[0]] = i;
        for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++)
        {
            prime[prime[j]*i] = i;
            if(i%prime[j]==0)
                break;
        }
    }
}

int main()
{
    getPrime();
    for(int i=0;i<100;i++)
        cout<<i<<' '<<prime[i]<<endl;
    return 0;
}