Prime Palindrome Problem
Description
LeetCode Problem 866.
Given an integer n, return the smallest prime palindrome greater than or equal to n.
An integer is prime if it has exactly two divisors: 1 and itself. Note that 1 is not a prime number.
- For example, 2, 3, 5, 7, 11, and 13 are all primes. An integer is a palindrome if it reads the same from left to right as it does from right to left.
- For example, 101 and 12321 are palindromes.
The test cases are generated so that the answer always exists and is in the range [2, 2 * 10^8].
Example 1:
1
2
Input: n = 6
Output: 7
Example 2:
1
2
Input: n = 8
Output: 11
Example 3:
1
2
Input: n = 13
Output: 101
Constraints:
- 1 <= n <= 10^8
Sample C++ Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
int evenPalindrome(int num) {
string str1 = to_string(num);
string str2 = str1;
reverse(str2.begin(), str2.end());
return stoi(str1 + str2);
}
int oddPlaindrome(int num) {
string str1 = to_string(num);
string str2 = str1.substr(0, str1.length() - 1);
reverse(str2.begin(), str2.end());
return stoi(str1 + str2);
}
bool isPrime(int num) {
if (num == 1) {
return false;
}
for (int i = 2; i * i <= num; ++i) {
if (num % i == 0) {
return false;
}
}
return true;
}
public:
int primePalindrome(int N) {
int even = 1;
int odd = 1;
int cur = 0;
do {
int evenp = evenPalindrome(even);
int oddp = oddPlaindrome(odd);
cur = min(evenp, oddp);
if (evenp < oddp) {
++even;
} else {
++odd;
}
} while (!(cur >= N && isPrime(cur)));
return cur;
}
};