Prime Palindrome

medium math number theory

Problem

Given an integer n, return the smallest prime palindrome greater than or equal to n. A number is a palindrome if it reads the same forwards and backwards, and prime if its only divisors are 1 and itself. (Note: every even-digit palindrome except 11 is divisible by 11, so the next prime palindrome past 11 always has an odd number of digits.)

Inputn = 6

Output7

7 is the first value ≥ 6 that is both a palindrome and prime.

def prime_palindrome(n):
    def is_prime(x):
        if x < 2: return False
        i = 2
        while i * i <= x:
            if x % i == 0: return False
            i += 1
        return True
    while True:
        s = str(n)
        if s == s[::-1] and is_prime(n):
            return n
        n += 1

function primePalindrome(n) {
  const isPrime = (x) => {
    if (x < 2) return false;
    for (let i = 2; i * i <= x; i++)
      if (x % i === 0) return false;
    return true;
  };
  while (true) {
    const s = String(n);
    if (s === [...s].reverse().join("") && isPrime(n)) return n;
    n++;
  }
}

int primePalindrome(int n) {
    while (true) {
        if (isPal(n) && isPrime(n)) return n;
        n++;
    }
}
private boolean isPal(int x) {
    String s = Integer.toString(x);
    return s.equals(new StringBuilder(s).reverse().toString());
}
private boolean isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; (long) i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; (long long) i * i <= x; i++)
        if (x % i == 0) return false;
    return true;
}
int primePalindrome(int n) {
    while (true) {
        string s = to_string(n), r(s.rbegin(), s.rend());
        if (s == r && isPrime(n)) return n;
        n++;
    }
}

Explanation

We want the smallest number that is both a palindrome and prime and at least n. The most direct idea is to just try every number starting from n upward and return the first one that passes both checks.

For each candidate, we do two quick tests. The palindrome test turns the number into a string s and checks if it equals its own reverse (s == s[::-1]). The prime test, is_prime, tries dividing by every i up to √x; if none divides it evenly, it is prime.

If a candidate passes both, we return it. Otherwise we add 1 and keep going. The loop is guaranteed to end because such numbers exist above any starting point.

Example: n = 6. We check 6 (palindrome but even, not prime), then 7 (a single digit, so a palindrome, and prime) — so the answer is 7.

A handy fact noted in the problem: aside from 11, every palindrome with an even number of digits is divisible by 11, so most candidates fail the prime test fast.

Time: O(answer · √answer) Space: O(1)