0866. 回文质数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 枚举回文数

1. 📝 题目描述

• leetcode

给你一个整数 n，返回大于或等于 n 的最小 回文质数。

一个整数如果恰好有两个除数：1 和它本身，那么它是 质数。注意，1 不是质数。

• 例如，2、3、5、7、11 和 13 都是质数。

一个整数如果从左向右读和从右向左读是相同的，那么它是 回文数。

• 例如，101 和 12321 都是回文数。

测试用例保证答案总是存在，并且在 [2, 2 * 10^8] 范围内。

---

示例 1：

输入：n = 6
输出：7

示例 2：

输入：n = 8
输出：11

示例 3：

输入：n = 13
输出：101

---

提示：

• 1 <= n <= 10^8

2. 🎯 s.1 - 枚举回文数

c

bool isPrime(int n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (long long i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}

int primePalindrome(int n) {
    if (n <= 2) return 2;
    if (n <= 3) return 3;
    if (n <= 5) return 5;
    if (n <= 7) return 7;
    if (n <= 11) return 11;
    for (int len = 3; len <= 9; len += 2) {
        int half = len / 2 + 1;
        int start = 1, end = 1;
        for (int i = 0; i < half - 1; i++) start *= 10;
        for (int i = 0; i < half; i++) end *= 10;
        for (int h = start; h < end; h++) {
            int digits[10], dLen = 0, tmp = h;
            while (tmp > 0) { digits[dLen++] = tmp % 10; tmp /= 10; }
            long long pal = h;
            for (int i = 1; i < dLen; i++) pal = pal * 10 + digits[i];
            if (pal >= n && isPrime((int)pal)) return (int)pal;
        }
    }
    return -1;
}

js

/**
 * @param {number} n
 * @return {number}
 */
var primePalindrome = function (n) {
  if (n <= 2) return 2
  if (n <= 3) return 3
  if (n <= 5) return 5
  if (n <= 7) return 7
  if (n <= 11) return 11
  for (let len = 3; len <= 9; len += 2) {
    const half = Math.floor(len / 2) + 1
    const start = Math.pow(10, half - 1)
    const end = Math.pow(10, half)
    for (let h = start; h < end; h++) {
      const s = String(h)
      const pal = Number(s + s.slice(0, -1).split('').reverse().join(''))
      if (pal >= n && isPrime(pal)) return pal
    }
  }
  return -1
}

function isPrime(n) {
  if (n < 2) return false
  if (n < 4) return true
  if (n % 2 === 0 || n % 3 === 0) return false
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false
  }
  return true
}

py

class Solution:
    def primePalindrome(self, n: int) -> int:
        def is_prime(x: int) -> bool:
            if x < 2: return False
            if x < 4: return True
            if x % 2 == 0 or x % 3 == 0: return False
            i = 5
            while i * i <= x:
                if x % i == 0 or x % (i + 2) == 0: return False
                i += 6
            return True
        if n <= 2: return 2
        if n <= 11:
            for x in [2, 3, 5, 7, 11]:
                if x >= n: return x
        for length in range(3, 10, 2):
            half = length // 2 + 1
            for h in range(10 ** (half - 1), 10 ** half):
                s = str(h)
                pal = int(s + s[-2::-1])
                if pal >= n and is_prime(pal):
                    return pal

• 时间复杂度：$O(N)$，其中 N 是答案大小
• 空间复杂度：$O(1)$

算法思路：

• 偶数位回文数（除 11 外）均能被 11 整除，只需枚举奇数位回文数
• 由前半部分生成回文数，判断是否为质数