P1865 A % B Problem 素数筛

　　

题目描述

区间质数个数

输入输出格式

输入格式：

一行两个整数 询问次数n，范围m

接下来n行，每行两个整数 l,r 表示区间

输出格式：

对于每次询问输出个数 t，如l或r∉[1,m]输出 Crossing the line

输入输出样例

输入样例#1： 复制

2 5
1 3
2 6

输出样例#1： 复制

2
Crossing the line

说明

【数据范围和约定】

对于20%的数据 1<=n<=10 1<=m<=10

对于100%的数据 1<=n<=1000 1<=m<=1000000 -10^9<=l<=r<=10^9 1<=t<=1000000

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);i--)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define LL long long
#define pb push_back
#define fi first
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
///////////////////////////////////
#define inf 0x3f3f3f3f
#define N 100000000+5
int s,e;
int f[N];
int a[N];

void prime()
{
    //0代表是素数  1代表不是素数  最好这样反过来 节省初始化为1的时间
    a[1]=1;
    for(int i=2;i*i<=e;i++)
    {
        if(a[i]==0)
            for(int j=i*i;j<=e;j+=i)
           a[j]=1;
    }
    rep(i,2,e)
    {
        f[i]=f[i-1];
        if(a[i]==0)f[i]++;
    }
}
int main()
{
    int n;
    RII(n,e);
    prime();
    rep(i,1,n)
    {
        int a,b;
        RII(a,b);
        if(a<1||b>e)printf("Crossing the line
");
        else printf("%d
",f[b]-f[a-1]);
    }
    return 0;
}