[leetcode] 866. Prime Palindrome

[leetcode] 866. Prime Palindrome

Description

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.

For example, 2,3,5,7,11 and 13 are primes.

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.

For example, 12321 is a palindrome.

Example 1:

Input: 6Output: 7

Example 2:

Input: 8Output: 11

Example 3:

Input: 13Output: 101

Note:

1 <= N <= 10^8The answer is guaranteed to exist and be less than 2 * 10^8.

分析

题目的意思是：给定N，找出大于N的最小回文素数。这道题我最能想到的就是暴力破解，觉得可能会超时。后面看了答案貌似也是以暴力求解，只是缩小了搜索空间。暴力破解就很简单了，从N出发一直往上找，直到找到第一个符合条件的结果为止。对于判断是否是素数，只需要判断1～sqrt(n)之间是否有整除的数就行了。

代码

class Solution: def isPrime(self,n): if(n==1): return False for i in range(2,int(n**.5)+1): if(n%i==0): return False return True def reverse(self,n): ans=0 while(n): ans=10*ans+n%10 n=n//10 return ans def primePalindrome(self, N: int) -> int: while(True): if((self.reverse(N)==N) and self.isPrime(N)): return N N+=1 if(N>10**7 and N<10**8): N=10**8

参考文献

​​回文素数​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。