素数表，区间素数筛

普通筛法

106 0.02 秒
 107 0.4秒
 108 5 秒

typedef long long LL;
const int LEN  = 1e9+1;
bool vis[LEN];
//int Prime[666666];
int cnt = 1;
void init(void)
{
    int n = 1e8*5;
    int m = sqrt(n)+1;
    for(int i = 2; i <= m; ++i)
    {
        if(!vis[i])
        {
// Prime[cnt++] = i;
            for(LL j = i *  i; j <= n; j += i)
                vis[j] = 1;
        }

    }
}

欧拉筛法

void Euler_s(void){
    int i,j,num = 1;
    memset(u,true,sizeof(u));
    for(int i = 2;i <= n; ++i){
        if(u[i]) su[num++] = i;
        for(j = 1; j < num; ++j){
            if(i*su[j] > n) break;
            u[i*su[j]] = false;
            if(i % su[j] == 0)
             break;
        }

    }
}

void Era_s(void){
    check[1] = 1;
    tot = 1;
    for(int i = 2;i < maxn; ++i){
        if(!check[i]){
        Prime[tot++] = i;    
        for(int j = i+i;j < maxn; ++j)  check[j] = 1;
        }
    } 
}
void Euler_s(void){
    check[1] = 1;
    tot = 1;
    int n = 1e6;
    for(int i = 2;i <= n; ++i){
         if(!check[i]) Prime[tot++] = i; 
         for(int j = 1;j < tot; ++j){
            if(i*Prime[j] > n) break;
            check[i*Prime[j]] = 1;
            if(i % Prime[j] == 0) break;
         }
    }
}

对比

当n < 1e7 时二者花费时间几乎相同
n >= 1e8 采用第二种

线性筛法的应用


const int maxn = 1e6+100;
bool check[maxn];
int phi[maxn],Prime[maxn];
void init(int MAXN){
    int N = maxn-1;
    memset(check,false,sizeof(check));
    phi[1] = 1;
    int tot = 0;
    for(int i = 2;i <= N; ++i){
        if(!check[i]){
            Prime[tot++] = i;
            phi[i] = i-1;
        }
        for(int j = 0;j < tot; ++j){
            if(i*Prime[j] > N) break;
            check[i*Prime[j]] = true;
            if(i%Prime[j] == 0){
                phi[i*Prime[j]] = phi[i]*Prime[j];
                break;
            }
            else{
                phi[i*Prime[j]] = phi[i]*(Prime[j]-1);
            }
        }
    }

}

应用举例

Help Hanzo LightOJ - 1197


const int LEN  = 1e6+1;
bool vis[LEN];
LL Prime[LEN];
int cnt = 1;
void init(void)
{
    int n = 70000;
    for(int i = 2; i <= n; ++i)
    {
        if(!vis[i])
        {
            Prime[cnt++] = i;
            for(LL j = (LL)i +  i; j <= n; j += i)
                vis[j] = 1;
        }

    }
}
bool  sign[200000];
int main(void)
{
    init();
    int T;
    cin>>T;
    int kase = 0;
    while(T--)
    {
        LL a,b;

        cin>>a>>b;
        int len = b-a+1;
        int num = 0;
        me(sign);
        int t = sqrt(b);
        for(int i = 1; i < cnt&&Prime[i] <= t; ++i)
        {
            LL tmp = max(a/Prime[i],(LL)2);
            if(tmp*Prime[i] < a)
                tmp++;
            while(tmp * Prime[i] <= b)
            {
                if(tmp*Prime[i]-a>100000)
                while(1);
                else
                sign[tmp*Prime[i]-a] = 1;
                tmp++;
            }
        }
        for(int i = 0; i < len; ++i)
        {
            if(!sign[i])
                num++;
        }
        if(a==1)
            num--;
        printf("Case %d: %d\n",++kase,num);
    }
    return 0;
}