题目描述

某古寺的一块石碑上依稀刻有一些三位与四位的神秘自然数。专家研究发现：这些数是素数，且从低位去掉1位或2位，3位……（直到就剩一个数）后都仍为素数，从高位去掉1位或2位，3位……（直到就剩一个数）后也都仍为素数，更奇妙的是同时去掉它的最高位与最低位数字后还是素数。因此，人们把这些神秘的素数称为金蝉素数，喻意为金蝉脱壳之后仍为美丽的金蝉。 现给出一个数n，找出n以内的金蝉素数。如果没有则输出"No"

输入

一行：整数n (100<n<9999)

输出

若干行，每行一个金蝉素数（从小到大排序）

样例输入 复制

500

样例输出 复制

373

67分代码：

//码风不好，有点啰嗦，请见谅TAT
#include<bits/stdc++.h>
using namespace std;
bool prime[10000001],pd=false;
int n,x[5];
int main(){
	cin>>n;
	prime[1]=1;
    for(int i=2;i<=n;i++)//i式素数筛选
        if(prime[i]==0)
            for(int j=i+i;j<=n;j=j+i)
                prime[j]=1;
    for(int i=100;i<=n;i++){
    	if(prime[i]==0){
    		x[1]=i%10;
    		x[2]=i/10%10;
    		x[3]=i/100%10;
    		x[4]=i/1000%10;
    		if(i<=999){
    			if(prime[x[3]]==1||prime[x[3]*10+x[2]]==1)continue;
    			if(prime[x[2]*10+x[1]]==1||prime[x[1]]==1)continue;
    			if(prime[x[2]]==1)continue;
			}
			else{
				if(prime[x[4]]==1||prime[x[4]*10+x[3]]==1||prime[x[4]*100+x[3]*10+x[2]]==1)continue;
    			if(prime[x[3]*100+x[2]*10+x[1]]==1||prime[x[2]*10+x[1]]==1||prime[x[1]]==1)continue;
    			if(prime[x[3]*10+x[2]]==1)continue;
			}
			cout<<i<<endl;
			pd=true;
		}
	}
	if(pd=false)cout<<"No";
    return 0;
}