题目背景
题目名称是吸引你点进来的
实际上该题还是很水的
题目描述
区间质数个数
输入格式
一行两个整数 询问次数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
素数(质数)的定义大家小学都学过:除了1和它本身没有其他约数的数叫素数,有其他约数的叫合数,1既不是素数,也不是合数;
(这个先搁置一边)
我们判断素数的程序大家应该都写过
#include<cstdio> using namespace std; long int n,m,i,j,l,r,a[1000005]; int main(){ scanf("%ld%ld",&n,&m); a[2]=1; for(i=3;i<=m;i++){ int x=0; for(j=2;j*j<=i;j++){ if(i%j==0){ x=1; break; } } if(x==1){ a[i]=a[i-1]; } else{ a[i]=a[i-1]+1; } } while(n--){ scanf("%ld%ld",&l,&r); if((l<1)||(r>m)){ printf("Crossing the line\n"); continue; } printf("%ld\n",a[r]-a[l-1]); } return 0; }
今天的文章A%B Problem分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/57525.html