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

1
2

Input: n = 6
Output: 7

Example 2

1
2

Input: n = 8
Output: 11

Example 3

1
2

Input: n = 13
Output: 101

Constraints

  • 1 <= n <= 10^8

Solution

Intuition

To find the smallest prime palindrome greater than or equal to n, we need to generate palindromic numbers and check if they are prime. Brute force checking every number is too slow for large n, so we generate palindromes efficiently and check each for primality. Odd-length palindromes are prioritized because all even-length palindromes (except 11) are divisible by 11 and thus not prime.

Approach

  1. For each possible length of palindrome (starting from the length of n), generate all palindromic numbers.
  2. For each palindrome >= n, check if it is prime.
  3. Return the first such number found.
  4. Special case: if n <= 2, return 2.

Code

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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 * 1LL * 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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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 * 1L * 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);
            int end = (int)Math.pow(10, (len + 1) / 2);
            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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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).