Formatted question description: https://leetcode.ca/all/866.html
866. Prime Palindrome (Medium)
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: 6 Output: 7
Example 2:
Input: 8 Output: 11
Example 3:
Input: 13 Output: 101
Note:
1 <= N <= 10^8- The answer is guaranteed to exist and be less than
2 * 10^8.
Related Topics:
Math
Solution 1.
// OJ: https://leetcode.com/problems/prime-palindrome/
// Time: O(N)
// Space: O(logN)
// Ref: https://leetcode.com/problems/prime-palindrome/solution/
class Solution {
bool isPrime(int x) {
if (x < 2) return false;
for (int d = 2, R = sqrt(x); d <= R; ++d) {
if (x % d == 0) return false;
}
return true;
}
public:
int primePalindrome(int N) {
for (int L = 1; L <= 5; ++L) {
for (int root = pow(10, L - 1); root < pow(10, L); ++root) { // check for odd-length palindromes
auto s = to_string(root);
for (int k = L - 2; k >= 0; --k) s += s[k];
int x = stoi(s);
if (x >= N && isPrime(x)) return x;
}
for (int root = pow(10, L - 1); root < pow(10, L); ++root) {
auto s = to_string(root);
for (int k = L - 1; k >= 0; --k) s += s[k];
int x = stoi(s);
if (x >= N && isPrime(x)) return x;
}
}
return -1;
}
};
Solution 2. Brute Force with Mathematical Shortcut
// OJ: https://leetcode.com/problems/prime-palindrome/
// Time: O(N)
// Space: O(1)
// Ref: https://leetcode.com/problems/prime-palindrome/solution/
class Solution {
bool isPrime(int x) {
if (x < 2) return false;
for (int d = 2, R = sqrt(x); d <= R; ++d) {
if (x % d == 0) return false;
}
return true;
}
int reverse(int N) {
int ans = 0;
while (N > 0) {
ans = 10 * ans + (N % 10);
N /= 10;
}
return ans;
}
public:
int primePalindrome(int N) {
while (true) {
if (N == reverse(N) && isPrime(N)) return N;
++N;
if (1e7 < N && N < 1e8) N = 1e8;
}
}
};
Java
class Solution {
public int primePalindrome(int N) {
int palindromeNum = nextPalindrome(N);
while (!isPrime(palindromeNum))
palindromeNum = nextPalindrome(palindromeNum + 1);
return palindromeNum;
}
public int nextPalindrome(int num) {
int length = String.valueOf(num).length();
if (num + 1 == (int) Math.pow(10, length))
return num + 2;
int divisor = (int) Math.pow(10, length / 2);
int headerNum = num / divisor;
boolean even = length % 2 == 0;
int palindromeNum = generatePalindrome(headerNum, even);
if (palindromeNum < num)
palindromeNum = generatePalindrome(headerNum + 1, even);
return palindromeNum;
}
public int generatePalindrome(int num, boolean even) {
StringBuffer sb1 = new StringBuffer(String.valueOf(num));
StringBuffer sb2 = new StringBuffer(String.valueOf(num));
sb2.reverse();
if (!even)
sb2.deleteCharAt(0);
String palindromeStr = new StringBuffer(sb1.toString()).append(sb2.toString()).toString();
return Integer.parseInt(palindromeStr);
}
public boolean isPrime(int num) {
if (num == 1)
return false;
if (num == 2 || num == 3)
return true;
if (num % 2 == 0 || num % 3 == 0)
return false;
int sqrt = (int) Math.sqrt(num);
for (int i = 5; i <= sqrt; i += 2) {
if (num % i == 0)
return false;
}
return true;
}
}