An integer is a palindrome if it reads the same from left to right as it does from right to left.
// Author: github.com/lzl124631x
// Time: O(lgN)
// Space: O(1)
bool isPalindrome(long n) {
long r = 0;
for (long tmp = n; tmp; tmp /= 10) r = r * 10 + tmp % 10;
return r == n;
}
// OJ: https://leetcode.com/problems/prime-palindrome/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
int getPalindrome(int half, bool odd) {
int pal = half;
if (odd) half /= 10;
for (; half; half /= 10) pal = pal * 10 + half % 10;
return pal;
}
bool isPrime(int n) {
if (n < 2) return false;
for (int d = 2; d * d <= n; ++d) {
if (n % d == 0) return false;
}
return true;
}
public:
int primePalindrome(int n) {
for (int len = 1; true; ++len) {
int begin = pow(10, (len - 1) / 2), end = pow(10, (len + 1) / 2);
for (int half = begin; half < end; ++half) {
int pal = getPalindrome(half, len % 2);
if (pal >= n && isPrime(pal)) return pal;
}
}
return -1;
}
};