蓝桥杯-超级质数

2023-03-04 14:36:41 浏览数 (1)

蓝桥杯-超级质数

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

0 人点赞