LeetCode Weekly 92：867. 回文素数
原创LeetCode Weekly 92：867. 回文素数
原创
杜逸先
发布于 2018-07-09 10:00:38
发布于 2018-07-09 10:00:38
先来看一下题目：
LeetCode 867. 回文素数
求出大于或等于 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。
分析
我当时做的时候是先写了一个生成器找素数，然后判断是不是回文数，素数生成器是这样的:
class Solution:
def get_primes(self):
primes = [2]
yield primes[0]
now = 3
while True:
if not any(now % prime == 0 for prime in primes if prime < now ** 0.5 + 1):
yield now
primes.append(now)
now += 1
def primePalindrome(self, N):
"""
:type N: int
:rtype: int
"""
primes = self.get_primes()
prime = next(primes)
while prime < N:
prime = next(primes)
is_palindrome = lambda s: str(s) == ''.join(list(str(s))[::-1])
while not is_palindrome(prime):
prime = next(primes)
return(prime)很遗憾这个方案超时了，因为在N很大的时候，他会找出所有比N小的素数，显然是不现实的。
我们仔细分析一下就会知道，其实回文数是比素数更苛刻的要求，因为10101的下一个回文数是10201，而这中间还有一百个数，其中自然会有素数。
另外找到下一个比N大的回文数比找下一个比N大的素数简单很多。具体的方案是这样子的：
- 如果N是回文数直接返回，
- 根据整数N产生三个字符串front，middle和end，其中front是前半部分，如果N的位数是奇数的话middle是中间的数字否则middle为空，end是front的逆序字符串，
- 判断front+middle+end拼成的整数是否比N大，是的话返回这个整数，
- 否的话查找下一个比(front + middle + 1) + end拼成的整数大的回文数。
例如寻找比122大的回文数：
- 122不是回文数，生成front=‘’1‘’，middle=‘’2‘’，end=‘’1‘’三个字符串，
- 生成的整数121比122小，开始找比131大的回文数，
- 132是回文数，返回。
我们不断根据这个方法找到新的回文数，然后判断是否为素数就可以了。
代码实现
def nextPalindrome(n):
is_palindrome = lambda s: str(s) == ''.join(list(str(s))[::-1])
if is_palindrome(n):
return n
original = str(n)
front = original[:len(original) // 2]
middle = original[len(original) // 2] if len(original) % 2 else ''
end = front[::-1]
mirror = int(front + middle + end)
if mirror > n:
return mirror
else:
return nextPalindrome(int(str(int(front + middle) + 1) + end))
def is_prime(n):
return not any(n % x == 0 for x in range(2, int(n ** 0.5) + 1))
class Solution:
def primePalindrome(self, N):
"""
:type N: int
:rtype: int
"""
find = False
n = nextPalindrome(N)
while not find:
if is_prime(n):
find = True
else:
n = nextPalindrome(n + 1)
return nN=10000的话结果是10301，这个算法只判断了10101，10201，10301三个数是不是素数，还是很高效的。如果是最初的算法，只是找到比10000大的素数就已经超时了。
结语
要善于把握不同的选择方案的成本，在这个例子中找下一个回文数的成本比找下一个素数的成本小得多。
最后祝大家享受生活，享受代码。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录