ACM-ICPC 2018沈阳赛区网络预赛 K题

A prime number (or a prime) is a natural number greater than 111 that cannot be formed by multiplying two smaller natural numbers.

Now lets define a number NNN as the supreme number if and only if each number made up of an non-empty subsequence of all the numeric digits of NNN must be either a prime number or 111.

For example, 171717 is a supreme number because 111, 777, 171717 are all prime numbers or 111, and 191919 is not, because 999 is not a prime number.

Now you are given an integer N (2≤N≤10100)N\ (2 \leq N \leq 10^{100})N (2≤N≤10100), could you find the maximal supreme number that does not exceed NNN?

Input

In the first line, there is an integer T (T≤100000)T\ (T \leq 100000)T (T≤100000) indicating the numbers of test cases.

In the following TTT lines, there is an integer N (2≤N≤10100)N\ (2 \leq N \leq 10^{100})N (2≤N≤10100).

Output

For each test case print "Case #x: y", in which xxx is the order number of the test case and yyy is the answer.

样例输入复制

2
6
100

样例输出复制

Case #1: 5
Case #2: 73

 

开始理解错了题意。。。。

本题求小于给出数n的superme number，就是说小于n的数且它的字串及本身都是素数的最大值。

不知道规律就先打表找规律

根据打表可知：所有的四位数都不属于superme number，而超过四位数的数子串里一定有四位数的数，则由此可知若给出的数超过了四位数，该数的最大superme number为317.

#include <iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
int judge(int n){
	int flag=1;
	for(int i=2;i<n;i++){
		if(n%i==0){
		flag=0;}
	}
	if(flag==1){
	return 1;
	}
	else{
		return 0;
	}
}
int main(){
	int n;
	char s[10001];
	scanf("%d",&n);
	for(int j=1;j<=n;j++){
	scanf("%s",s);
	int len=strlen(s);
	//int n;
	//scanf("%d",&n);
	if(len>=4){
		printf("Case #%d: %d\n",j,317);
		continue;
	}
	else{
	int ss=atol(s);//将字符串转换为长整型
	int i;
	int a,b,c,d;
	for(int i=ss;i>=2;i--){
		a=i/1000;
		b=i/100%10;
		c=i/10%10;
		d=i%10;
		if(judge(a)&&judge(b)&&judge(c)&&judge(d)&&judge(c+b*10)&&judge(b+a*10)&&judge(a*10+c)&&judge(a*10+d)&&judge(b*10+d)&&judge(c+b*10+a*100)&&judge(b*100+c*10+d)&&judge(d+c*10+b*100+a*1000)&&judge(a*100+c*10+d)&&judge(a*100+b*10+d)){//所有字串情况
		printf("Case #%d: %d\n",j,i);
			break;
		}
	}
	}
	}
}