866. 回文质数

题目描述

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

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

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

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

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

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

示例 1：

输入：n = 6
输出：7

示例 2：

输入：n = 8
输出：11

示例 3：

输入：n = 13
输出：101

提示：

1 <= n <= 10⁸

解法

方法一

思考

求不小于 \(n\) 的最小回文素数。\(n\) 达 \(10^8\)，从 \(n\) 起逐个判断素数在最坏情况下偏慢，但偶数位数回文必被 \(11\) 整除。

因此在 \((10^7,10^8)\) 直接跳到 \(10^8\)。其余情况递增并同时检测回文与素性，保证找到的第一个即答案。

Python3JavaC++Go

class Solution:
    def primePalindrome(self, n: int) -> int:
        def is_prime(x):
            if x < 2:
                return False
            v = 2
            while v * v <= x:
                if x % v == 0:
                    return False
                v += 1
            return True

        def reverse(x):
            res = 0
            while x:
                res = res * 10 + x % 10
                x //= 10
            return res

        while 1:
            if reverse(n) == n and is_prime(n):
                return n
            if 10**7 < n < 10**8:
                n = 10**8
            n += 1

class Solution {
    public int primePalindrome(int n) {
        while (true) {
            if (reverse(n) == n && isPrime(n)) {
                return n;
            }
            if (n > 10000000 && n < 100000000) {
                n = 100000000;
            }
            ++n;
        }
    }

    private boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int v = 2; v * v <= x; ++v) {
            if (x % v == 0) {
                return false;
            }
        }
        return true;
    }

    private int reverse(int x) {
        int res = 0;
        while (x != 0) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
}

class Solution {
public:
    int primePalindrome(int n) {
        while (1) {
            if (reverse(n) == n && isPrime(n)) return n;
            if (n > 10000000 && n < 100000000) n = 100000000;
            ++n;
        }
    }

    bool isPrime(int x) {
        if (x < 2) return false;
        for (int v = 2; v * v <= x; ++v)
            if (x % v == 0)
                return false;
        return true;
    }

    int reverse(int x) {
        int res = 0;
        while (x) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        return res;
    }
};

func primePalindrome(n int) int {
    isPrime := func(x int) bool {
        if x < 2 {
            return false
        }
        for v := 2; v*v <= x; v++ {
            if x%v == 0 {
                return false
            }
        }
        return true
    }

    reverse := func(x int) int {
        res := 0
        for x != 0 {
            res = res*10 + x%10
            x /= 10
        }
        return res
    }
    for {
        if reverse(n) == n && isPrime(n) {
            return n
        }
        if n > 10000000 && n < 100000000 {
            n = 100000000
        }
        n++
    }
}

866. 回文质数

题目描述

解法

方法一

评论