866. 回文质数

Medium

题目描述

给定一个整数 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

解题思路

这道题需要找到大于等于 n 的最小回文质数。直接暴力枚举所有数字并检查是否既是回文又是质数会超时，需要优化。

关键观察：

对于偶数位的回文数（除了11），都可以被11整除，因此不是质数
我们主要关注奇数位的回文数

解题思路：

首先处理小于等于11的特殊情况
对于更大的数，生成奇数位回文数并检查是否为质数
回文数生成：取前半部分，镜像到后半部分形成回文
质数检查：只需检查到 √n

算法步骤：

处理边界情况（n <= 11）
从n开始，找到第一个大于等于n的奇数位数的长度
生成该长度的回文数，从最小的开始
对每个回文数检查是否为质数
返回找到的第一个回文质数

这种方法避免了检查偶数位回文数，大大减少了搜索空间。

代码实现

class Solution {
public:
    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;
        
        // 找到 n 的位数
        int len = to_string(n).length();
        if (len % 2 == 0) len++; // 确保是奇数位
        
        while (true) {
            int palindrome = getNextPalindrome(n, len);
            if (isPrime(palindrome)) {
                return palindrome;
            }
            len += 2; // 跳到下一个奇数位长度
            n = pow(10, len - 1); // 更新 n 为该位数的最小值
        }
    }
    
private:
    int getNextPalindrome(int n, int len) {
        int half_len = (len + 1) / 2;
        int start = pow(10, half_len - 1);
        int end = pow(10, half_len) - 1;
        
        for (int i = start; i <= end; i++) {
            int palindrome = makePalindrome(i, len % 2 == 1);
            if (palindrome >= n) {
                return palindrome;
            }
        }
        return -1;
    }
    
    int makePalindrome(int half, bool isOdd) {
        string s = to_string(half);
        string rev = s;
        reverse(rev.begin(), rev.end());
        if (isOdd) {
            rev = rev.substr(1);
        }
        return stoi(s + rev);
    }
    
    bool isPrime(long long n) {
        if (n <= 1) return false;
        if (n <= 3) 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;
    }
};

class Solution:
    def primePalindrome(self, n: int) -> int:
        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
        
        # 找到 n 的位数
        length = len(str(n))
        if length % 2 == 0:
            length += 1  # 确保是奇数位
        
        while True:
            palindrome = self.getNextPalindrome(n, length)
            if self.isPrime(palindrome):
                return palindrome
            length += 2  # 跳到下一个奇数位长度
            n = 10 ** (length - 1)  # 更新 n 为该位数的最小值
    
    def getNextPalindrome(self, n, length):
        half_len = (length + 1) // 2
        start = 10 ** (half_len - 1)
        end = 10 ** half_len - 1
        
        for i in range(start, end + 1):
            palindrome = self.makePalindrome(i, length % 2 == 1)
            if palindrome >= n:
                return palindrome
        return -1
    
    def makePalindrome(self, half, isOdd):
        s = str(half)
        rev = s[::-1]
        if isOdd:
            rev = rev[1:]
        return int(s + rev)
    
    def isPrime(self, n):
        if n <= 1: return False
        if n <= 3: return True
        if n % 2 == 0 or n % 3 == 0: return False
        
        i = 5
        while i * i <= n:
            if n % i == 0 or n % (i + 2) == 0:
                return False
            i += 6
        return True

public class Solution {
    public 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;
        
        int length = n.ToString().Length;
        if (length % 2 == 0) length++;
        
        while (true) {
            int palindrome = GetNextPalindrome(n, length);
            if (IsPrime(palindrome)) {
                return palindrome;
            }
            length += 2;
            n = (int)Math.Pow(10, length - 1);
        }
    }
    
    private int GetNextPalindrome(int n, int length) {
        int halfLen = (length + 1) / 2;
        int start = (int)Math.Pow(10, halfLen - 1);
        int end = (int)Math.Pow(10, halfLen) - 1;
        
        for (int i = start; i <= end; i++) {
            int palindrome = MakePalindrome(i, length % 2 == 1);
            if (palindrome >= n) {
                return palindrome;
            }
        }
        return -1;
    }
    
    private int MakePalindrome(int half, bool isOdd) {
        string s = half.ToString();
        char[] arr = s.ToCharArray();
        Array.Reverse(arr);
        string rev = new string(arr);
        if (isOdd) {
            rev = rev.Substring(1);
        }
        return int.Parse(s + rev);
    }
    
    private bool IsPrime(long n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        if (n % 2 == 0 || n % 3 == 0) return false;
        
        for (long i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) {
                return false;
            }
        }
        return true;
    }
}

function isPrime(num) {
    if (num < 2) return false;
    if (num === 2) return true;
    if (num % 2 === 0) return false;
    for (let i = 3; i * i <= num; i += 2) {
        if (num % i === 0) return false;
    }
    return true;
}

function isPalindrome(num) {
    const str = num.toString();
    return str === str.split('').reverse().join('');
}

function getNextPalindrome(num) {
    const str = num.toString();
    const len = str.length;
    const isOdd = len % 2 === 1;
    const mid = Math.floor(len / 2);
    
    let left = str.slice(0, isOdd ? mid + 1 : mid);
    let right = left.slice(0, mid).split('').reverse().join('');
    let palindrome = parseInt(left + right);
    
    if (palindrome >= num) {
        return palindrome;
    }
    
    let leftNum = parseInt(left) + 1;
    left = leftNum.toString();
    
    if (left.length > (isOdd ? mid + 1 : mid)) {
        return parseInt('1' + '0'.repeat(len - 1) + '1');
    }
    
    while (left.length < (isOdd ? mid + 1 : mid)) {
        left = '0' + left;
    }
    
    right = left.slice(0, mid).split('').reverse().join('');
    return parseInt(left + right);
}

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;
    
    if (n.toString().length % 2 === 0) {
        n = parseInt('1' + '0'.repeat(n.toString().length - 1) + '1');
    }
    
    let candidate = getNextPalindrome(n);
    
    while (true) {
        if (isPrime(candidate)) {
            return candidate;
        }
        candidate = getNextPalindrome(candidate + 1);
    }
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	分析
时间复杂度	O(√P × log P)，其中 P 是结果回文数。生成回文数为 O(log P)，质数检查为 O(√P)
空间复杂度	O(log P)，用于存储数字的字符串表示

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目