求一亿以内的回文质数

题目

求一亿以内的回文质数。

思路

先求质数再判断回文，效率低下。所以先构造回文数，再判断质数。

再观察回文数中哪些可以提前排除。

比如：

• 大于 2 的偶数一定是合数，所以只构建奇数回文数即可。
• 偶数位长度的回文数都能被 11 整除，比如 1331。所以偶数位的回文数除了 11 都是合数。
• 一个 \(k\) 位数，可以构造出一个 \(2 * k + 1\)位的回文数。比如 13，可以构造 131；189 可以构造 18981。所以 100000000 内的只要从 1 构造到 9999 即可。

public class Solution {

    public List<Integer> PalindromePrimeNum(String[] args) {
        List<Integer> res = new ArrayList<>();
        res.add(11);
        StringBuilder builder;
        for (int i = 12; i <= 9999; i++) {
            builder = new StringBuilder(String.valueOf(i));
            if ((builder.charAt(0) - '0') % 2 == 0) {
                // 首位是偶数，回文后也会是偶数
                continue;
            }
            // 拼接回文数
            int len = builder.length();
            StringBuilder right = new StringBuilder(builder.substring(0, len - 1));
            builder.append(right.reverse());
            int palindromeNum = Integer.parseInt(builder.toString());
            if (checkPrimeNumber(palindromeNum)) {
                res.add(palindromeNum);
            }
        }
        return res;
    }

    public boolean checkPrimeNumber(int num) {
        // 判断是不是质数
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
}