##### Welcome to Subscribe On Youtube

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.

• class Solution {
public int primePalindrome(int N) {
}

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;
}

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;
}
}

############

class Solution {
public int primePalindrome(int n) {
while (true) {
if (reverse(n) == n && isPrime(n)) {
return n;
}
if (n > 10000000 && n < 100000000) {
n = 100000000;
}
++n;
}
}

private boolean isPrime(int x) {
if (x < 2) {
return false;
}
for (int v = 2; v * v <= x; ++v) {
if (x % v == 0) {
return false;
}
}
return true;
}

private int reverse(int x) {
int res = 0;
while (x != 0) {
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
}

• // OJ: https://leetcode.com/problems/prime-palindrome/
// Time: O(N)
// Space: O(logN)
// Ref: https://leetcode.com/problems/prime-palindrome/solution/
class Solution {
int getPalindrome(int half, bool odd) {
string s = to_string(half);
for (int i = s.size() - 1 - odd; i >= 0; --i) s += s[i];
return stoi(s);
}
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; len <= 5; ++len) {
for (int root = pow(10, len - 1); root < pow(10, len); ++root) { // Enumerate odd-length palindromes
int pal = getPalindrome(root, true);
if (pal >= n && isPrime(pal)) return pal;
}
for (int root = pow(10, len - 1); root < pow(10, len); ++root) { // Enumerate even-length palindromes
int pal = getPalindrome(root, false);
if (pal >= n && isPrime(pal)) return pal;
}
}
return -1;
}
};

• class Solution:
def primePalindrome(self, n: int) -> int:
def is_prime(x):
if x < 2:
return False
v = 2
while v * v <= x:
if x % v == 0:
return False
v += 1
return True

def reverse(x):
res = 0
while x:
res = res * 10 + x % 10
x //= 10
return res

while 1:
if reverse(n) == n and is_prime(n):
return n
if 10**7 < n < 10**8:
n = 10**8
n += 1


• func primePalindrome(n int) int {
isPrime := func(x int) bool {
if x < 2 {
return false
}
for v := 2; v*v <= x; v++ {
if x%v == 0 {
return false
}
}
return true
}

reverse := func(x int) int {
res := 0
for x != 0 {
res = res*10 + x%10
x /= 10
}
return res
}
for {
if reverse(n) == n && isPrime(n) {
return n
}
if n > 10000000 && n < 100000000 {
n = 100000000
}
n++
}
}