ACM-ICPC 2018 沈阳赛区网络预赛 K. Supreme Number（打表找规律）

题目链接：https://nanti.jisuanke.com/t/31452

样例输入 
2
6
100
样例输出 
Case #1: 5
Case #2: 73

 题意：supreme number的定义是：一个数的任意子串都是素数或者1（不连续），求不超过N的最大的supreme number

思路：一位数符合的有：1 2 3 5 7；两位数符合的有：11 13 17 23 31 37 53 71 73；三位数符合的有：113 131 137 173 311 317；四位数没有符合的。任意的四位数都不符合，那么只要超过四位的数字，定能找到一个四位数的子串，即定有不是素数的子串，所以只要超过四位数，答案就是317. 

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
typedef long long ll;

int main(){
	int t;
	scanf("%d",&t);
	int c=1;
	while(t--){
		char s[110];
		scanf("%s",s);
		int len=strlen(s);
		printf("Case #%d: ",c++);
		if(len>=4)printf("317\n");
		else if(len==1){
			int x=s[0]-'0';
			if(x==2)printf("2\n");
			else if(x==3)printf("3\n");
			else if(x==4)printf("3\n");
			else if(x==5)printf("5\n");
			else if(x==6)printf("5\n");
			else printf("7\n");
		}
		else if(len==2){
			int x=s[0]-'0';
			int y=s[1]-'0';
			int num=x*10+y;
			if(num<11)printf("7\n");
			else if(num<13)printf("11\n");
			else if(num<17)printf("13\n");
			else if(num<23)printf("17\n");
			else if(num<31)printf("23\n");
			else if(num<37)printf("31\n");
			else if(num<53)printf("37\n");
			else if(num<71)printf("53\n");
			else if(num<73)printf("71\n");
			else printf("73\n");
		}
		else{
			int x=s[0]-'0';
			int y=s[1]-'0';
			int z=s[2]-'0';
			int num=x*100+y*10+z;
			if(num<113)printf("73\n");
			else if(num<131)printf("113\n");
			else if(num<137)printf("131\n");
			else if(num<173)printf("137\n");
			else if(num<311)printf("173\n");
			else if(num<317)printf("311\n");
			else printf("317\n");
		}
	}
	return 0;
}