First Prime That Reads Both Ways

Medium

You are given an integer start. Find the smallest number that is at least start, is prime, and reads the same from left to right and from right to left (a palindrome). A prime is greater than 1 and divisible only by 1 and itself, e.g. 2, 3, 5, 7, 11, 13. Examples of palindromes are 7, 353 and 10301. The answer is guaranteed to exist and to be at most 2 · 10⁸.

Example 1

start=14 → 101

The two-digit palindromes 22, 33, …, 99 are all multiples of 11, while 101 is prime.

Example 2

start=4 → 5

4 is composite, and the single-digit 5 is prime and trivially a palindrome.

Example 3

start=132 → 151

141 = 3 · 47 is composite, while the next palindrome, 151, is prime.

Constraints

1 ≤ start ≤ 10⁸

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Math Number Theory

Similar problems

Primes Below a Bound Medium Laser in a Mirror Room Medium N-th Number Divisible by One of Three Medium Reduced Fractions Up to a Denominator Medium K-th Smallest Divisor Medium

Input

start=14

Expected

Run checks the first 3 tests in your browser. Submit checks all 47 tests on the server, hidden ones included.