We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Prime Palindrome

Difficulty: Medium

Problem Description

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. An integer is a palindrome if it reads the same from left to right as it does from right to left.

Key Insights

  • A prime number has exactly two divisors: 1 and itself.
  • A palindrome reads the same forwards and backwards.
  • The search space for the solution is bounded by [2, 2 * 10^8].
  • Efficient checking for primality and palindrome properties is essential.

Space and Time Complexity

Time Complexity: O(k * sqrt(m)), where k is the number of candidates checked (which can be large) and m is the maximum number being checked for primality. Space Complexity: O(1), as we are using a constant amount of extra space.

Solution

To solve the problem, we can use a brute-force approach that involves checking each number starting from n. For each number, we will first check if it is a palindrome. If it is a palindrome, we will then check if it is prime.

  1. Palindrome Check: Convert the number to a string and compare it to its reverse.
  2. Prime Check: Use trial division up to the square root of the number to check for primality.
  3. Iterate: Start from n and check each number until we find a number that is both prime and a palindrome.

Code Solutions

def is_palindrome(num):
    return str(num) == str(num)[::-1]

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def prime_palindrome(n):
    while True:
        if is_palindrome(n) and is_prime(n):
            return n
        n += 1
← Back to All Questions