题目背景

题目名称是吸引你点进来的

实际上该题还是很水的

题目描述

区间质数个数

输入输出格式

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

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

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

输入输出样例

2 51 32 6

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

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5  6 using namespace std; 7 bool bp[1000000 + 5]; 8 int prime[1000000 + 5]; 9 int sum[1000000 + 5];10 11 int cmp(int x,int y)12 {13     return x>y?1:0;14 }15 16 void makep(int n)//线性筛 17 {18     int cnt = 1;19     for(int i = 2;i <= n;i ++)20     {21         if(!bp[i]) prime[cnt] = i,++ cnt;22         //bp记录一个数是否被筛去 23         for(int j = 1;j <= cnt;j ++)24         {25             if(i * prime[j] > n)  break;26             bp[i*prime[j]] = 1;27             if(i % prime[j] == 0)  break;28         }29     }30 }31 32 int main()33 {34     int m,n,l,r;35     scanf("%d%d",&n,&m);36     makep(m);37     sum[1] = 0;//前缀和，sum[i]记录[0,i]的素数个数 38     for(int i = 2;i <= m;i ++)39     {40         if(!bp[i])41             sum[i]++;42         sum[i] += sum[i-1];43     }44     int ans = 0;45     for(int i = 0;i < n;i ++)46     {47         scanf("%d%d",&l,&r);48         if(l > m || l < 1 || r > m || r < 1)49         {//超出范围 50             printf("Crossing the line\n");51             continue;52         }53         ans = sum[r-1] - sum[l-1];//由于sum从0开始，l、r都要-1 54         if(!bp[r]) ans ++;//如果端点也是素数，需要++ 55         printf("%d\n",ans);56     }57     return 0;58 }