蓝桥杯-超级质数
- 1、问题描述
- 2、解题思路
- 3、代码实现
1、问题描述
如果一个质数 P 的每位数字都是质数, 而且每两个相邻的数字组成的两位 数是质数, 而且每三位相邻的数字组成的三位数是质数, 依次类推, 如果每相邻的 k 位数字组成的 k 位数都是质数, 则 P 称为超级质数。
如果把超级质数 P 看成一个字符串, 则这个超级质数的每个子串都是质 数。
例如, 53 是一个超级质数。
请问, 最大的超级质数是多少?
答案提交
这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
2、解题思路
这次用的方法感觉有点像暴力解法，我们直接将Integer类型转成String类型，然后对该字符串的每个字符进行遍历(只有质数才会进行遍历，否则直接跳过)，这里需要遍历字符串的时候需要两层for循环，因为我们需要不断去截取字符串，并判断截取的字符串是否是质数，若每次截取下来的都是质数，则说明该数是超级质数，然后用一个临时变量保存下就行。
3、代码实现
先编写一个判断质数的函数
代码语言：javascript复制 public static boolean isPrime(int num){
if (num==1)
return false;
for (int i = 2; i <=Math.sqrt(num); i ) {
if(num%i==0)
return false;
}
return true;
}主函数代码如下：
代码语言：javascript复制public static void main(String[] args) {
int max=53;
for (int i = max; i <Math.sqrt(Integer.MAX_VALUE); i ) {
boolean flag=false;
String s = String.valueOf(i);
if(!isPrime(i)){ //不是质数的结束本次循环
continue;
}
for (int j = 0; j < s.length(); j ) {
for (int k =j; k < s.length(); k ) {
if(k 1<=s.length()){
int temp=Integer.parseInt(s.substring(j,k 1));
if(isPrime(temp)){
flag=true;
}else{
flag=false; //只要有一个不满足条件，跳出最内层循环
break;
}
}
}
if(!flag){ //跳出第二层循环
break;
}
}
if(flag){
max=Math.max(max,i);
}
}
System.out.println(max);
}运行结果：
代码解释：
第一层for循环是我们需要遍历的数字，其实没有Integer.MAX_VALUE这么大，不超时就行。
然后设置一个标志位=false，如果当前数字不是质数，直接结束本次循环。
两次for循环是为了不断去截取不同长度并且相邻的字符串，然后去判断截取之后的数字是否为质数，若是设置flag=true，否则flag=false,用break跳出本次循环，跳出最内层的for循环之后，在判断flag是否为true，若是true，则需要将他的值和max比较，保留最大的超级质数，若flag=false，则继续跳出本层循环。
