Supreme Number

2024-01-24 13:58

文章标签 number supreme

本文主要是介绍Supreme Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Supreme Number

题目描述：
A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.
Now lets define a number N as the supreme number if and only if each number made up of an non-empty subsequence of all the numeric digits of N must be either a prime number or 1.
For example, 17 is a supreme number because 1, 7, 17 are all prime numbers or 1, and 19 is not, because 9 is not a prime number.
Now you are given an integer N (2≤N≤10100), could you find the maximal supreme number that does not exceed N?
输入：
In the first line, there is an integer T(T≤100000) indicating the numbers of test cases.
In the following T lines, there is an integer N (2≤N≤10100).
输出：
For each test case print “Case #x: y”, in which x is the order number of the test case and y is the answer.
样例输入：
2
6
100
样例输出：
Case #1: 5
Case #2: 73
题目大意：输入一个数字，输出一个素数，要求其满足以下条件：
1.小于等于输入的数；
2.其每一位仍未素数；
3.其相连的几位数字组成的新数仍为素数。
这题要是暴力解的话，就要先打表（素数），然后对其进行分解，保证其满足所有条件，然后再输出最大的，这样写理论可行，但是会T（博主写这个暴力解法写了170多行会乱说？）最后发现其实是有规律的。不管数字是多少，都只可能有20种输出(别问我哪来的，通过暴力的代码无意间试出来的)。

#include<bits/stdc++.h>
using namespace std;
int n;
char s[105];
int a[20] = {1, 2, 3, 5, 7, 11, 13, 17, 23, 31, 37, 53, 71, 73, 113, 131, 137, 173, 311, 317};//就是这20个
int main()
{scanf("%d",&n);for (int j = 1; j <= n; j++){scanf("%s",s);if(strlen(s) >= 4)//大于四位，一定输出317{printf("Case #%d: 317\n", j);continue;}int n = 0;for(int i = 0; s[i]!='\0' ; i++){n = n * 10;n = n + s[i] - '0';}int v = 0;for(int i = 0; i < 20; i++){if(n >= a[i]){v = a[i];}else{break;}}printf("Case #%d: %d\n", j, v);}return 0;
}