0866：回文质数（1938 分）

力扣第 92 场周赛第 3 题

题目

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

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

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

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

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

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

示例 1：

输入：n = 6
输出：7

示例 2：

输入：n = 8
输出：11

示例 3：

输入：n = 13
输出：101

提示：

• 1 <= n <= 108

分析

#1

类似 0479 ，可以直接从小到大构造回文数，再判断是否符合即可。注意遍历顺序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

def primePalindrome(self, N):
	def is_prime(n):
		return n >= 2 and all(n % i for i in range(2, int(n**0.5)+1))

	for L in range(1, 6):
		for is_odd in [1, 0]:
			for half in range(10**(L-1), 10**L):
				n = int(str(half) + str(half)[-is_odd-1::-1]) 
				if n >= N and is_prime(n):
					return n

200 ms

#2

还有个巧妙的优化。可以证明偶数位回文数必然是 11 的倍数。

• 设一个数 x 表示为 $\overline{…a_5 a_4 a_3 a_2 a_1}$，那么：

$$x = a_1 + 10 * a_2 + 100 * a_3 + 1000 * a_4 + 10000 * a_5 + … $$ $$x = a_1 + (11-1) * a_2 + (99+1) * a_3 + (1001-1) * a_4 + (9999+1) * a_5 + … $$ $$x = (a_1 - a_2 + a_3 - a_4 + a_5 - …) + 11 * a_2 + 99 * a_3 + 1001 * a_4 + 9999 * a_5 + …$$

• 偶数位的 $\overline{9…9}$ 显然是 11 的倍数。

• 偶数位(设为 2 * k 位)的 $\overline{10…01}$ 等于 2 * k 位的 $\overline{11…11}$ 减去 10 乘以 2 * (k-1) 位的 $\overline{11…11}$，显然也是 11 的倍数。

• 所以：

  $$x \ mod \ 11 = (a_1 - a_2 + a_3 - a_4 + a_5 - …) \ mod \ 11 $$

• 偶数位回文数的 奇位数字之和与偶位数字之和的差 为 0，故偶数位回文数必然是 11 的倍数

所以先排除 11 的情况，然后只需要考虑一种镜像方式即可。

还可以优化为从 N 的回文根开始遍历。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def primePalindrome(self, N):
	def is_prime(n):
		return n >= 2 and all(n%i for i in range(2, int(n**0.5) + 1))

	if 8<=N<=11:
		return 11
	L = len(str(N))
	h = int(str(N)[:(L+1)//2])
	for half in range(h, 10**6):
		n = int(str(half) + str(half)[-2::-1]) 
		if n >= N and is_prime(n):
			return n

56 ms