Abstract / Summary

Find the largest prime number that is also a palindrome and less than or equal to a given number n.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 28% (100k+ submissions).

Typical patterns to solve this problem:

• Math
• Number Theory

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the classic “prime palindrome” problem: given an integer n, find the smallest palindrome greater than or equal to n that is also a prime. The solution is organized around a lazy generator that produces palindromic numbers in increasing order, combined with a straightforward primality test that checks only odd divisors. Early returns handle trivial inputs, and the generator’s internal state is tuned to avoid unnecessary work, such as constructing even-length palindromes that are guaranteed to be composite (except for the number 2).

Core Workflow

Handling the trivial lower bound

if n <= 2:
    return 2

When the input is 0, 1, or 2, the function immediately returns 2, the smallest prime palindrome. This branch eliminates the need for any further computation for the smallest possible inputs.

Palindrome generator definition

def palindromes():
    i   = 0
    odd = True
    threshold = 10
    while True:
        # one more digit
        if i == threshold:
            if odd:
                # reset count but allow one more digit in the second half
                i //= 10
                odd = False
            else:
                # increase threshold, skip middle digit
                odd = True
                threshold *= 10

        # build palindrome
        one = str(i)
        two = one[::-1]
        if odd:
            two = two[1:]
        yield int(one + two)

        i += 1

The generator yields an infinite sequence of palindromes. It maintains three variables:

• i - the current base number whose string representation is mirrored.
• odd - a flag indicating whether the palindrome should have odd length.
• threshold - the power of ten at which the digit count of i increases.

When i reaches threshold, the generator toggles the odd flag and adjusts i to start constructing the next length of palindromes. For odd-length palindromes the middle digit is omitted from the mirrored part (two = two[1:]). The concatenation of one and two yields the full palindrome, which is emitted as an integer.

Iterating over generated palindromes

for x in palindromes():
    if x >= n and (x & 1) == 1:   # skip even palindromes because they can't be primes
        # basic prime test
        p = 3
        prime = True
        while p*p <= x:
            if x % p == 0:
                prime = False
                break
            p += 2

        if prime:
            return x

The loop consumes palindromes one by one. The condition x >= n ensures that only candidates not smaller than the input are considered. The bitwise test (x & 1) == 1 discards even palindromes, which are never prime except for the already-handled value 2.

When a candidate passes these filters, a simple trial-division primality test runs. Starting from divisor 3, the loop increments by 2, thereby testing only odd divisors. The loop terminates as soon as a divisor is found (prime = False) or when the square of the divisor exceeds the candidate, at which point the candidate is declared prime and returned.

Edge Cases Addressed

The code explicitly handles the lower bound where n is less than or equal to 2, returning 2 without invoking the generator.

Even-length palindromes are implicitly avoided for primality checks because the generator produces both odd and even length palindromes, but the subsequent filter (x & 1) == 1 removes all even numbers, including even-length palindromes that are necessarily divisible by 11 when their length exceeds one digit.

The generator’s threshold logic ensures that when the digit count of i grows, the palindrome length alternates between odd and even, preventing an infinite stretch of numbers with the same digit count. This design gracefully handles the transition from single-digit to multi-digit palindromes.

The primality loop stops at the square root of the candidate, guaranteeing correctness even for large numbers without overshooting.

Performance Optimizations

The most significant optimization is the use of a lazy palindrome generator. By constructing palindromes on demand, the algorithm avoids generating the entire set up to a large bound, which would consume both time and memory.

Skipping even palindromes early ((x & 1) == 1) eliminates roughly half of the candidates before any expensive primality testing occurs.

The primality test itself is streamlined: it starts at 3 and increments by 2, thereby halving the number of division operations compared to testing every integer. The early break on finding a divisor prevents unnecessary iterations once compositeness is detected.

The generator’s internal state management (i //= 10 when moving from odd to even length) reuses the already computed prefix, reducing the amount of string manipulation required to build the next palindrome.

By yielding palindromes in strictly increasing order, the algorithm guarantees that the first prime palindrome found is the minimal solution, allowing an immediate return without scanning further candidates.

Overall, the combination of on-the-fly palindrome construction, early elimination of even numbers, and a minimal trial-division loop yields a solution that scales well for the typical input ranges encountered in algorithmic challenges.

Imagine a magical machine that makes special numbers. Some numbers, called palindromes, look exactly the same whether you read them forward or backward, like names that don't change when flipped around. Other numbers, called primes, are like tiny building blocks that cannot be broken into smaller equal groups.

This code works like a clever detective searching for a specific number. First, it starts a process that builds those mirror-image palindromes one by one. It creates a never-ending line of them, starting from small ones and growing larger and larger.

Once the machine has a palindrome, the detective checks to see if it is big enough by comparing it to the starting target number. If the palindrome is big enough, the detective does a little experiment to see if it is a prime number. To do this, the detective tries to divide the number by smaller numbers to see if it fits perfectly. If the number refuses to be divided by anything other than one and itself, the detective knows a special prime palindrome has been found. The loop keeps going until the perfect match is discovered and unveiled.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java				Python	TS
	WalkCCC	C++		Java				Python
	leetcode.ca	C++		Java			Go	Python
	LeetcodeHelp	C++		Java				Python
	Progiez	C++		Java				Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	JoshCrozier		JS
	ruoru				Rust
	suxrobGM					C#
	varunu28			Java
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
JoshCrozier	JavaScript
ruoru	Rust
suxrobGM	C#
varunu28	Java
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality