这是一道入坑题,因为按照常规思路,很容易【时间超限】

问题描述

农民约翰母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组成一个质数。
 
例如有四根肋骨的数字分别是:7  3  3  1,那么全部肋骨上的数字  7331是质数;三根肋骨  733是质数;二根肋骨  73  是质数;当然,最后一根肋骨  7  也是质数。7331  被叫做长度  4  的特殊质数。
 
写一个程序对给定的肋骨的数目  N  (1< =N< =8),求出所有的特殊质数。数字1不被看作一个质数。


输入

单独的一行包含N。


输出

按顺序输出长度为  N  的特殊质数,每行一个。


样例输入

4


样例输出

2333
2339
2393
2399
2939
3119
3137
3733
3739
3793
3797
5939
7193
7331
7333
7393
(不以空格结尾)


首先我拿到这个题目,噼里啪啦敲出了以下代码:


 

import java.util.Scanner;
public class Main {
    public static boolean isPrime(int n) {
        if (n == 0 || n == 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        // 从最小的n位数开始
        int a = (int) Math.pow(10, n - 1);
        // 从最小的n+1位数结束
        int b = (int) Math.pow(10, n);
        int temp;
        // flag:标记第一行是否打出,以便控制程序不会多输出一空行
        boolean bl, flag = false;
        for (int i = a; i < b; i++) {
            bl = true;
            temp = i;
            while (temp > 0) {
                if (isPrime(temp)) {
                    temp /= 10;
                } else {
                    bl = false;
                    break;
                }
            }
            // 如果是第一行输出,那么输出之前不打出换行符
            if (bl && !flag) {
                System.out.print(i);
                flag = true;
            }
            //如果不是第一行输出,那么每次输出数字之前都先换个行
            if (bl && flag) {
                System.out.print("\n" + i);
            }
        }
    }
}

结果出现


正解如下:
 
首先要明确,第一位数字要单独判断是否是质数,那么第一位数字肯定是2,3,5,7
其次,观察1——100的质数

我们发现,除了第一位,后面的数字必须是1,3,7,9
 
代码如下:


import java.util.Scanner;
public class Main {
    static int temp;
    static int N;
    /**
     * 标记第一行是否打出,以便控制程序不会多输出一空行
     */
    static boolean bl = false;
    static int[] arr1 = new int[]{2, 3, 5, 7};
    static int[] arr2 = new int[]{1, 3, 7, 9};
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        // 每个符合条件的数字第一位肯定是2,3,5,所以这里用arr1
        for (int i = 0; i < 4; i++) {
            dfs(arr1[i], 1);
        }
    }
    /**
     * 递归
     */
    private static void dfs(int num, int len) {
        // 当数字长度已经达到N,输出
        if (len == N) {
            //为了控制整个程序输出没有多余的一空行
            if (!bl) {
                System.out.print(num);
                bl = true;
            } else {
                System.out.print("\n" + num);
            }
        }
        // 追加一位,乘10
        num *= 10;
        // 除了第一位,后面的几位数肯定是1,3,7,9 ,所以这里用arr2
        for (int i = 0; i < 4; i++) {
            //变成多了一位的数字
            temp = num + arr2[i];
            //判断其是不是素数,如果是的话,就再往后追加一位,再判断,直到长度够为止
            if(isPrime(temp)){
                dfs(temp, len + 1);
            }
        }
    }
    /**
     * 高效率判断素数
     */
    private static boolean isPrime(int temp) {
        if (temp < 2) {
            return false;
        }
        if (temp == 2 || temp == 3) {
            return true;
        }
        if (temp % 6 != 1 && temp % 6 != 5) {
            return false;
        }
        for (int i = 5; i <= (int) Math.sqrt(temp); i += 6) {
            if (temp % i == 0 || temp % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

 
百分百通过
算法里面的高效率判断素数方法,链接在文章【不同方法判断素数】

您必须 登录 才能发表评论