题目描述

求出大于或等于 N 的最小回文素数。

回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。

例如，2，3，5，7，11 以及 13 是素数。

回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。

例如，12321 是回文数。

样例

输入：6
输出：7

输入：8
输出：11

输入：13
输出：101

注意

• 1 <= N <= 10^8
• 答案肯定存在，且小于 2 * 10^8。

算法

(暴力枚举) $O(N)$

1. 我们从最小的回文数开始逐一枚举，直到找到一个大于等于 N 的素数为止。
2. 这里有一个结论，除 11 以外，偶数长度的回文数不可能是素数。这里用到了被 11 整除的数的性质，奇数位之和等于偶数位之和的数一定能被 11 整除。
3. 枚举的过程可以使用技巧，我们枚举奇数长度回文数的前半部分，这样第一次遇到素数且大于 N 就可以停下了。

时间复杂度

• 由于最多有 $O(\sqrt(N))$ 个数字需要枚举，每次判定素数需要 $O(sqrt(N))$ 的时间，故时间复杂度为 $O(N)$。

空间复杂度

• 生成回文数时需要空间存放临时字符串，故空间复杂度为 $O(\log N)$。

C++ 代码

class Solution {
public:

    bool check(int x) {
        if (x < 2 || (x > 2 && x % 2 == 0))
            return false;
        for (int i = 3; i * i <= x; i += 2)
            if (x % i == 0)
                return false;
        return true;
    }

    int make(int x) {
        string s = to_string(x), t = s;
        reverse(t.begin(), t.end());
        s.pop_back();
        return stoi(s + t);
    }

    int primePalindrome(int N) {
        if (N > 7 && N <= 11)
            return 11;

        for (int i = 1; i <= 99999; i++) {
            int x = make(i);
            if (x >= N && check(x))
                return x;
        }

        return -1;
    }
};