Welcome to Subscribe On Youtube

866. Prime Palindrome

Description

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

Solutions

• Java
• C++
• Python
• Go

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

• class Solution {
  public:
      int primePalindrome(int n) {
          while (1) {
              if (reverse(n) == n && isPrime(n)) return n;
              if (n > 10000000 && n < 100000000) n = 100000000;
              ++n;
          }
      }
  
      bool isPrime(int x) {
          if (x < 2) return false;
          for (int v = 2; v * v <= x; ++v)
              if (x % v == 0)
                  return false;
          return true;
      }
  
      int reverse(int x) {
          int res = 0;
          while (x) {
              res = res * 10 + x % 10;
              x /= 10;
          }
          return res;
      }
  };
  

• 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++
  	}
  }
  

All Problems

All Solutions