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.
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.
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 <= 108The key idea in #866 Prime Palindrome is to efficiently find the smallest number greater than or equal to n that is both a palindrome and a prime. A brute-force approach would check every number for both properties, but this becomes slow as numbers grow.
A better strategy is to generate palindromes directly and then test whether each candidate is prime. An important mathematical observation is that even-length palindromes (except 11) are divisible by 11, so they cannot be prime. Because of this, most solutions only generate odd-length palindromes, drastically reducing the search space.
You can construct palindromes by taking a prefix and mirroring it to form the full number, then check if the result is greater than or equal to n and verify primality using trial division up to sqrt(x). This approach significantly improves efficiency compared to scanning all numbers.
Time complexity mainly depends on the number of generated palindromes and the cost of primality testing.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Generate Palindromes + Prime Check | O(k * sqrt(p)) where k is number of palindrome candidates | O(1) |
| Brute Force Check Each Number | O(n * sqrt(n)) | O(1) |
ThePrimeTime
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, problems like Prime Palindrome appear in technical interviews because they combine number theory, math observations, and efficient search techniques. They test a candidate's ability to reduce brute-force work using mathematical insights.
The optimal approach is to generate palindrome numbers directly and test them for primality. By constructing palindromes from a numeric prefix and mirroring it, you avoid checking all integers. Additionally, skipping even-length palindromes (except 11) greatly reduces the search space.
Most implementations use trial division to test primality. The number is checked for divisibility up to the square root of the candidate value, which is efficient enough because only a limited number of palindrome candidates are tested.
Even-length palindromes are always divisible by 11, which means they cannot be prime except for the number 11 itself. Because of this mathematical property, most solutions only generate odd-length palindromes to improve efficiency.