埃及筛法

int pri[MAXN],num=0;
bool vis[MAXN];
long long sum[MAXN],a[MAXN];
void init()
{
    int i,j;
    for(i=2;i<MAXN;i++)
    {
        if(vis[i]==false)pri[num++]=i;
        for(j=0;j<num&&i*pri[j]<MAXN;j++)
        {
            vis[i*pri[j]]=true;
            if(i%pri[j]==0)break;
        }
    }
}

区间筛法

给定整数a和b，请问区间[a,b)内有多少个素数？

bool is_prime[MAX_L];
bool is_prime_small[MAX_SQRT_B];
//对区间[a,b]内的整数执行筛法。is_prime[i-a]=true:i是素数
void segment_sieve(long long a,long long b)
{
    long long i,j;
    for(i=0;i*i<b;i++)is_prime_small[i]=true;
    for(i=0;i<b-a;i++)is_prime[i]=true;
    for(i=2;i*i<b;i++)
    {
        if(is_prime_small[i])
        {
            for(j=2*i;j*j<b;j=j+i)is_prime_small[j]=false;   //筛[2,√b]
            //(a+i-1)/i得到最接近a的i的倍数，最低是i的2倍，然后筛选
            for(j=max(2,(a+i-1)/i)*i;j<b;j=j+i)is_prime[j-a]=false;   //筛[a,b)
        }
    }
}