0866-回文素数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:45:43 2023-09-13 16:45:43 Updated    

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

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

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

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

例如，12321 是回文数。

示例 1：

**输入：** 6
**输出：** 7

示例 2：

**输入：** 8
**输出：** 11

示例 3：

**输入：** 13
**输出：** 101

提示：

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

方法一： 遍历回文串

思路

假设有一个回文串 X，下一个回文串是什么？

每个 d 长度的回文串都有一个 回文根，回文根为前 k = d+1/2 个数字。下一个回文串一定是由下一个回文根组成的。

举个例子，如果 123 是 12321 的回文根，那么下一个回文串 12421 的回文根就是 124。

需要注意一个回文根可能对应两个回文串，例如 123321，12321 的回文根就都是 123。

算法

对于每个 回文根，找对应的两个回文串（一个奇数长度，一个偶数长度）。对于 k 长度的回文根，会产生长度为 2k - 1 和 2k - 1 的回文串。

当检查回文串的时候，需要先检查小的 2k - 1 长度的，这里直接把数字变成字符串来检查是否对称。

至于检查素数，这里用的是常见的 O(\sqrt{N}) 复杂度的算法来检查是不是素数，即检查小于 \sqrt{N 的数中有没有能整除 N 的。

[solution1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int primePalindrome(int N) {
        for (int L = 1; L <= 5; ++L) {
            //Check for odd-length palindromes
            for (int root = (int)Math.pow(10, L - 1); root < (int)Math.pow(10, L); ++root) {
                StringBuilder sb = new StringBuilder(Integer.toString(root));
                for (int k = L-2; k >= 0; --k)
                    sb.append(sb.charAt(k));
                int x = Integer.valueOf(sb.toString());
                if (x >= N && isPrime(x))
                    return x;
                    //If we didn't check for even-length palindromes:
                    //return N <= 11 ? min(x, 11) : x
            }

            //Check for even-length palindromes
            for (int root = (int)Math.pow(10, L - 1); root < (int)Math.pow(10, L); ++root) {
                StringBuilder sb = new StringBuilder(Integer.toString(root));
                for (int k = L-1; k >= 0; --k)
                    sb.append(sb.charAt(k));
                int x = Integer.valueOf(sb.toString());
                if (x >= N && isPrime(x))
                    return x;
            }
        }

        throw null;
    }

    public boolean isPrime(int N) {
        if (N < 2) return false;
        int R = (int) Math.sqrt(N);
        for (int d = 2; d <= R; ++d)
            if (N % d == 0) return false;
        return true;
    }
}
[solution1-Python]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def primePalindrome(self, N):
        def is_prime(n):
            return n > 1 and all(n%d for d in xrange(2, int(n**.5) + 1))

        for length in xrange(1, 6):
            #Check for odd-length palindromes
            for root in xrange(10**(length - 1), 10**length):
                s = str(root)
                x = int(s + s[-2::-1]) #eg. s = '123' to x = int('12321')
                if x >= N and is_prime(x):
                    return x
                    #If we didn't check for even-length palindromes:
                    #return min(x, 11) if N <= 11 else x

            #Check for even-length palindromes
            for root in xrange(10**(length - 1), 10**length):
                s = str(root)
                x = int(s + s[-1::-1]) #eg. s = '123' to x = int('123321')
                if x >= N and is_prime(x):
                    return x

复杂度分析

  • 时间复杂度： O(N)，其中大于最大 N 的素数为 100030001，这决定了时间复杂度的上限。

  • 空间复杂度： O(\log N)。

方法二： 数学法

算法

遍历所有数字，检查是不是回文串。如果是，检查是不是素数，如果当前数字长度为 8，可以跳过检查，因为不存在 8 长度的素数。

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int primePalindrome(int N) {
        while (true) {
            if (N == reverse(N) && isPrime(N))
                return N;
            N++;
            if (10_000_000 < N && N < 100_000_000)
                N = 100_000_000;
        }
    }

    public boolean isPrime(int N) {
        if (N < 2) return false;
        int R = (int) Math.sqrt(N);
        for (int d = 2; d <= R; ++d)
            if (N % d == 0) return false;
        return true;
    }

    public int reverse(int N) {
        int ans = 0;
        while (N > 0) {
            ans = 10 * ans + (N % 10);
            N /= 10;
        }
        return ans;
    }
}

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def primePalindrome(self, N):
        def is_prime(n):
            return n > 1 and all(n % d for d in xrange(2, int(n**.5) + 1))

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

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

复杂度分析

  • 时间复杂度： O(N)。

  • 空间复杂度： O(1)。

 Comments
On this page
0866-回文素数