蓝桥杯-超级质数

@toc

1、问题描述

如果一个质数 P 的每位数字都是质数, 而且每两个相邻的数字组成的两位 数是质数, 而且每三位相邻的数字组成的三位数是质数, 依次类推, 如果每相邻的 k 位数字组成的 k 位数都是质数, 则 P 称为超级质数。

如果把超级质数 P 看成一个字符串, 则这个超级质数的每个子串都是质 数。

例如, 53 是一个超级质数。

请问, 最大的超级质数是多少?

答案提交

这是一道结果填空的题, 你只需要算出结果后提交即可。本题的结果为一 个整数, 在提交答案时只填写这个整数, 填写多余的内容将无法得分。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

2、解题思路

这次用的方法感觉有点像暴力解法，我们直接将Integer类型转成String类型，然后对该字符串的每个字符进行遍历(只有质数才会进行遍历，否则直接跳过)，这里需要遍历字符串的时候需要两层for循环，因为我们需要不断去截取字符串，并判断截取的字符串是否是质数，若每次截取下来的都是质数，则说明该数是超级质数，然后用一个临时变量保存下就行。

3、代码实现

先编写一个判断质数的函数

 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;
    }

主函数代码如下：

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，则继续跳出本层循环。