题目背景
题目名称是吸引你点进来的
实际上该题还是很水的
题目描述
区间质数个数
输入输出格式
输入格式： 一行两个整数 询问次数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<cstdio> #include<iostream> using namespace std; int n,m; int a[1000009]; bool f[1000009]; int main(){ scanf("%d%d",&n,&m); f[1]=1; for(int i=2;i*i<=m;i++) if(f[i]==0) for(int j=2;j<=m/i;j++) f[i*j]=1; for(int i=1;i<=m;i++) a[i]=a[i-1]+(1-f[i]); for(int i=1;i<=n;i++){ int x,y; scanf("%d%d",&x,&y); if(x<1||y>m){ printf("Crossing the line\n"); continue; } printf("%d\n",a[y]-a[x-1]); } return 0; }