Prime Palindrome

Problem

Given an integer n, return _the smallestprime 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].

Examples

Example 1

Input: n = 6
Output: 7

Example 2

Input: n = 8
Output: 11

Example 3

Input: n = 13
Output: 101

Constraints

• 1 <= n <= 10^8

Solution

Method 1 - Generate Palindromes (Odd-length first)

Intuition

To find the smallest prime palindrome greater than or equal to n, generate palindromic numbers (pal) and check if they are prime. Brute-forcing every integer is too slow for large n, so we efficiently generate palindromes and test each pal for primality. We prioritize odd-length palindromes because even-length palindromes (except 11) are divisible by 11 and thus not prime.

Approach

1. For each palindrome len (number of digits) starting from the length of n, generate palindromes by constructing a root (the left half) and reflecting it to form pal.
2. For each root in the range start..end-1, build left = string of root and right = reverse of left without its last digit, then pal = int(left + right).
3. If pal >= n and pal is prime, return pal.
4. Special cases: return 2 if n <= 2; return 11 if 8 <= n <= 11 (since even-length palindromes aren't prime except 11).

Code

C++

bool isPrime(int x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;
    for (int i = 3; i * i <= x; i += 2) {
        if (x % i == 0) return false;
    }
    return true;
}

int primePalindrome(int n) {
    if (n <= 2) return 2;
    if (n >= 8 && n <= 11) return 11;
    for (int len = 1; len <= 9; ++len) {
        int start = pow(10, (len - 1) / 2), end = pow(10, (len + 1) / 2);
        for (int root = start; root < end; ++root) {
            string left = to_string(root);
            string right = left.substr(0, left.size() - 1);
            reverse(right.begin(), right.end());
            int pal = stoi(left + right);
            if (pal >= n && isPrime(pal)) return pal;
        }
    }
    return -1;
}

Go

import (
    "math"
    "strconv"
)

func isPrime(x int) bool {
    if x < 2 {
        return false
    }
    if x == 2 {
        return true
    }
    if x%2 == 0 {
        return false
    }
    for i := 3; i*i <= x; i += 2 {
        if x%i == 0 {
            return false
        }
    }
    return true
}

func primePalindrome(n int) int {
    if n <= 2 {
        return 2
    }
    if n >= 8 && n <= 11 {
        return 11
    }
    for l := 1; l <= 9; l++ {
        start := int(math.Pow(10, float64((l-1)/2)))
        end := int(math.Pow(10, float64((l+1)/2)))
        for root := start; root < end; root++ {
            left := strconv.Itoa(root)
            right := left[:len(left)-1]
            // reverse right
            r := []rune(right)
            for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
                r[i], r[j] = r[j], r[i]
            }
            pal, _ := strconv.Atoi(left + string(r))
            if pal >= n && isPrime(pal) {
                return pal
            }
        }
    }
    return -1
}

Java

class Solution {
    private boolean isPrime(int x) {
        if (x < 2) return false;
        if (x == 2) return true;
        if (x % 2 == 0) return false;
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) return false;
        }
        return true;
    }
    public int primePalindrome(int n) {
        if (n <= 2) return 2;
        if (n >= 8 && n <= 11) return 11;
        for (int len = 1; len <= 9; ++len) {
            int start = (int)Math.pow(10, (len - 1) / 2.0);
            int end = (int)Math.pow(10, (len + 1) / 2.0);
            for (int root = start; root < end; ++root) {
                String left = Integer.toString(root);
                String right = new StringBuilder(left.substring(0, left.length() - 1)).reverse().toString();
                int pal = Integer.parseInt(left + right);
                if (pal >= n && isPrime(pal)) return pal;
            }
        }
        return -1;
    }
}

Kotlin

fun isPrime(x: Int): Boolean {
    if (x < 2) return false
    if (x == 2) return true
    if (x % 2 == 0) return false
    var i = 3
    while (i * i <= x) {
        if (x % i == 0) return false
        i += 2
    }
    return true
}

fun primePalindrome(n: Int): Int {
    if (n <= 2) return 2
    if (n in 8..11) return 11
    for (len in 1..9) {
        val start = Math.pow(10.0, ((len - 1) / 2).toDouble()).toInt()
        val end = Math.pow(10.0, ((len + 1) / 2).toDouble()).toInt()
        for (root in start until end) {
            val left = root.toString()
            val right = left.substring(0, left.length - 1).reversed()
            val pal = (left + right).toInt()
            if (pal >= n && isPrime(pal)) return pal
        }
    }
    return -1
}

Python

def is_prime(x: int) -> bool:
    if x < 2:
        return False
    if x == 2:
        return True
    if x % 2 == 0:
        return False
    i = 3
    while i * i <= x:
        if x % i == 0:
            return False
        i += 2
    return True

def primePalindrome(n: int) -> int:
    if n <= 2:
        return 2
    if 8 <= n <= 11:
        return 11
    for length in range(1, 10):
        start = 10 ** ((length - 1) // 2)
        end = 10 ** ((length + 1) // 2)
        for root in range(start, end):
            left = str(root)
            right = left[:-1][::-1]
            pal = int(left + right)
            if pal >= n and is_prime(pal):
                return pal
    return -1

Rust

fn is_prime(x: i32) -> bool {
    if x < 2 {
        return false;
    }
    if x == 2 {
        return true;
    }
    if x % 2 == 0 {
        return false;
    }
    let mut i = 3;
    while i * i <= x {
        if x % i == 0 {
            return false;
        }
        i += 2;
    }
    true
}

fn prime_palindrome(n: i32) -> i32 {
    if n <= 2 {
        return 2;
    }
    if n >= 8 && n <= 11 {
        return 11;
    }
    for len in 1..=9 {
        let start = 10_i32.pow(((len - 1) / 2) as u32);
        let end = 10_i32.pow(((len + 1) / 2) as u32);
        for root in start..end {
            let left = root.to_string();
            let right: String = left.chars().take(left.len() - 1).rev().collect();
            let pal = format!("{}{}", left, right).parse::<i32>().unwrap();
            if pal >= n && is_prime(pal) {
                return pal;
            }
        }
    }
    -1
}

TypeScript

function isPrime(x: number): boolean {
    if (x < 2) return false;
    if (x === 2) return true;
    if (x % 2 === 0) return false;
    for (let i = 3; i * i <= x; i += 2) {
        if (x % i === 0) return false;
    }
    return true;
}

export function primePalindrome(n: number): number {
    if (n <= 2) return 2;
    if (n >= 8 && n <= 11) return 11;
    for (let len = 1; len <= 9; ++len) {
        const start = Math.pow(10, Math.floor((len - 1) / 2));
        const end = Math.pow(10, Math.floor((len + 1) / 2));
        for (let root = start; root < end; ++root) {
            const left = root.toString();
            const right = left.slice(0, -1).split('').reverse().join('');
            const pal = parseInt(left + right);
            if (pal >= n && isPrime(pal)) return pal;
        }
    }
    return -1;
}

Complexity

• ⏰ Time complexity: O(sqrt(N) * logN) for each palindrome checked, but the number of palindromes generated is much less than N. The overall runtime is efficient for the given constraints.
• 🧺 Space complexity: O(1) (ignoring output and call stack for string operations).