题目描述

区间质数个数

输入输出格式

输入格式：

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

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

输出格式：

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

输入输出样例

输入样例#1：

2 51 32 6

输出样例#1：

2Crossing 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

【分析】:不用前缀和就TLE阿QAQ

【代码】：

#include 
      
       using namespace std;int const MAX = 505;int const INF = 0x3fffffff;int n, m;int a[1000005];int isP(int n){    if(n == 1) return 0;    for(int i=2; i<=sqrt(n); i++){        if(n % i == 0){            return 0;        }    }    return 1;}int main(){    cin >> n >> m;    a[1] = 0;    int l, r, ans = 0;        for(int i=2; i<=m; i++){        if( i%2!=0 || i==2){            a[i] = a[i-1] + isP(i);        }        else{            a[i] = a[i-1];        }    }    //a[i]=isP(i)+a[i-1]是a[i]=a[i]前所有素数的个数，如果i是素数 a[i]要加一，否则不加（判素数的函数回的是1或0）     while(n--){        ans = 0;        cin >> l >> r;        if(l<1||r>m){            printf("Crossing the line\n");        }        else{            printf("%d\n",a[r] - a[l-1]);        }    }}
      

 

#include 
      
       using namespace std;int const MAX = 1000005;int const INF = 0x3fffffff;int n, m, l, r;int a[MAX];int sum[MAX];int main(){    cin >> n >> m;    a[1] = 1;    for(int i=2; i<=sqrt(m); i++){        if(!a[i]){            for(int j=i+i; j<=m; j+=i){                a[j] = 1;            }        }    }    for(int i=1; i<=m; i++){        sum[i] = sum[i-1] + (a[i]^1);//异或 ：a[i] = 0 ——> +1 / a[i] =  ——> +0    }    for(int i=1; i<=n; i++){        cin >> l >> r;        if(l<1 || r>m) puts("Crossing the line");        else{            printf("%d\n",sum[r]-sum[l-1]);        }    }}