Algorithm


Problem Name: 866. Prime Palindrome

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 * 108].

 

Example 1:

Input: n = 6
Output: 7

Example 2:

Input: n = 8
Output: 11

Example 3:

Input: n = 13
Output: 101

 

Constraints:

  • 1 <= n <= 108

Code Examples

#1 Code Example with Java Programming

Code - Java Programming


class Solution {
  public int primePalindrome(int N) {
    for (int i = 1; i  < = 5; i++) {
      for (int root = (int)Math.pow(10, i - 1); root  <  (int)Math.pow(10, i); root++) {
        StringBuilder sb = new StringBuilder(Integer.toString(root));
        for (int j = i - 2; j >= 0; j--) {
          sb.append(sb.charAt(j));
        }
        int num = Integer.valueOf(sb.toString());
        if (num >= N && isPrime(num)) {
          return num;
        }
      }
      for (int root = (int)Math.pow(10, i - 1); root  <  (int)Math.pow(10, i); root++) {
        StringBuilder sb = new StringBuilder(Integer.toString(root));
        for (int j = i - 1; j >= 0; j--) {
          sb.append(sb.charAt(j));
        }
        int num = Integer.parseInt(sb.toString());
        if (num >= N && isPrime(num)) {
          return num;
        }
      }
    }
    return -1;
  }
  
  private boolean isPrime(int n) {
    if (n  <  2) {
      return false;
    }
    for (int j = 2; j  < = (int) Math.sqrt(n); j++) {
      if (n % j == 0) {
        return false;
      }
    }
    return true;
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 6

Output

x
+
cmd
7

#2 Code Example with Javascript Programming

Code - Javascript Programming


const primePalindrome = function(n) {
  if(n >= 8 && n <= 11> return 11
  const rev = str => str.split('').reverse().join('')
  for (let i = 1; i  <  1e5; i++) {
    let left = `${i}`, right = rev(left).slice(1)
    let num = +(left + right)
    if (num >= n && isPrime(num)) return num
  }
  return -1

  function isPrime(num) {
    if(num < 2 || num % 2 === 0) return num === 2
    for(let i = 3; i * i  < = num; i += 2) {
      if(num % i === 0> return false
    }
    return true
  }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 6

Output

x
+
cmd
7

#3 Code Example with Python Programming

Code - Python Programming

start coding...
class Solution:
    def primePalindrome(self, N):
        def isPrime(x):
            if x < 2 or x % 2 == 0: return x == 2
            for i in range(3, int(x**0.5) + 1, 2):
                if x % i == 0: return False
            return True
        if 8 <= N <= 11: return 11
        for x in range(10 ** (len(str(N)) // 2), 10**5):
            y = int(str(x) + str(x)[-2::-1])
            if y >= N and isPrime(y): return y
Copy The Code & Try With Live Editor

Input

x
+
cmd
n = 8

Output

x
+
cmd
11
Advertisements

Demonstration


Previous
#865 Leetcode Smallest Subtree with all the Deepest Nodes Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#867 Leetcode Transpose Matrix Solution in C, C++, Java, JavaScript, Python, C# Leetcode