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
, and13
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
and12321
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
Output
#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
Output
#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
Output