蓝桥杯-超级质数
- 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
,则继续跳出本层循环。