class Solution {
public:
int primePalindrome(int n) {
}
};
866. 回文素数
求出大于或等于 N 的最小回文素数。
回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。
例如，2，3，5，7，11 以及 13 是素数。
回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。
例如，12321 是回文数。
示例 1：
输入：6 输出：7
示例 2：
输入：8 输出：11
示例 3：
输入：13 输出：101
提示：
1 <= N <= 10^82 * 10^8。
原站题解
java 解法, 执行用时: 37 ms, 内存消耗: 37.8 MB, 提交时间: 2023-06-29 09:46:07
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;
}
}
python3 解法, 执行用时: 160 ms, 内存消耗: 15.9 MB, 提交时间: 2023-06-29 09:44:10
class Solution:
def primePalindrome(self, N: int) -> int:
def is_prime(n):
return n > 1 and all(n%d for d in range(2, int(n**.5) + 1))
for length in range(1, 6):
#Check for odd-length palindromes
for root in range(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 range(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
java 解法, 执行用时: 45 ms, 内存消耗: 41.9 MB, 提交时间: 2023-06-29 09:42:54
/**
* 遍历回文串
* 找到回文根，k长度回文根对应回文串长度2k-1和2k
**/
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;
}
}