A36053. 迷信的病人
填空题
中等
知识点
题目描述
迷信的病人
题目描述
医院为了方便对患者进行建档和管理，引入了9位整数ID号来标识每个病人。最近医院入住了一个迷信的病人，他认为ID号的好坏直接决定了自己的命运。他对ID号x有如下要求:
（1）x的前三位数构成的整数是素数
（2）x的后三位数构成的整数是平方数（所谓平方数，是指它是某一个正整数的平方，e.g. 1,4,9,16...）
（3）x中不包含"13"
为了避免不必要的医患矛盾，医院须尽量满足他的需求。现给定正整数区间[m,n]，请你判断存在几个满足病人需求的ID号。
输入
两个正整数m，n，以空格隔开。(999999999>=n>=m>=111111111)
输出
一个整数（满足要求的ID的个数）。
样例输入
157689476 157689687样例输出
5提示
存在5个满足要求的ID：157689484,157689529,157689576,157689625,157689676
参考答案
#include<bits/stdc++.h>
using namespace std;
bool zs(int n){
if(n<2) return 0;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0){
return 0;
}
}
return 1;
}
bool check(int n){
int a=0,b;
while(n!=0){
b=n%10;
if(a==3&&b==1){
return 0;
}
a=b;
n=n/10;
}
return 1;
}
int main(){
int m,n,i,cnt=0;
int a[1010],aa=0,b[1010],bb=0;
cin>>m>>n;
for(i=100;i<1000;i++){
if(zs(i)==1){
a[aa]=i;
aa++;
}
}
for(i=1;i<1000;i++){
if((int)sqrt(i)==sqrt(i)){
b[bb]=i;
bb++;
}
}
int shu=0;
for(i=0;i<aa;i++){
for(int j=0;j<1000;j++){
for(int k=0;k<bb;k++){
shu=a[i]*1000000+j*1000+b[k];
if(shu>=m&&shu<=n&&check(shu)){
cnt++;
}
}
}
}
cout<<cnt;
return 0;
}
上一题
下一题