【算法】猫扑素数

发表于 | 分类于 | 阅读次数:

求自然数n内所有猫扑素数

  • 猫扑数：指以2开头，后面跟任意个3的十进制数。如：2、23、233等。

  • 素数（质数）：在大于1的自然数中，除了1和它本身以外不再有其他因数，这样的数称为素(质)数。

  • 合数：自然数中除能被1和本数整除外，还能被其他的数整除的数。如果一个数是合数，那么它的最小质因数肯定小于等于他的平方根。例如：50，最小质因数是2，2<50的开根号，
    再比如：15，最小质因数是3，3<15的开根号。。

  • 1和0既非素数也非合数。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public static void main(String[] args) {
        MopPrime obj = new MopPrime();
        for (int i = 0; i < Integer.MAX_VALUE; i++) {
            if (obj.isMopPrime(i)) {
                System.out.println(" 猫扑素数 ：" + i);
            }
        }
    }
    private boolean isMopPrime(int n) {
        return isMop(n) && isPrime(n);
    }
    private boolean isMop(int n) {
        if (n < 10) {
            return n == 2;
        } else {
            // 从后往前按位依次检查
            return (n % 10 == 3) && isMop(n / 10);
        }
    }
    private boolean isPrime(int n) {
        boolean flag = true;
        if (n < 2) {
            flag = false; //素数不小于2
        } else {
            // 如果一个数是合数，那么它的最小质因数肯定小于等于他的平方根。
            for (int i = 2; i <= Math.sqrt(n); i++) {
                if (n % i == 0) {
                    flag = false;
                    break;
                }
            }
        }
        return flag;
    }

判断素数的方法还可优化。思路：找规律避免无用判断。

0%