Prime Palindrome Problem


Description

LeetCode Problem 866.

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.

  • For example, 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.
  • For example, 101 and 12321 are palindromes.

The test cases are generated so that the answer always exists and is in the range [2, 2 * 10^8].

Example 1:

1
2
Input: n = 6
Output: 7

Example 2:

1
2
Input: n = 8
Output: 11

Example 3:

1
2
Input: n = 13
Output: 101

Constraints:

  • 1 <= n <= 10^8


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    int evenPalindrome(int num) {
        string str1 = to_string(num);
        string str2 = str1;
        reverse(str2.begin(), str2.end());
        return stoi(str1 + str2);
    }

    int oddPlaindrome(int num) {
        string str1 = to_string(num);
        string str2 = str1.substr(0, str1.length() - 1);
        reverse(str2.begin(), str2.end());
        return stoi(str1 + str2);
    }

    bool isPrime(int num) {
        if (num == 1) {
            return false;
        }
        for (int i = 2; i * i <= num; ++i) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    
public:
    int primePalindrome(int N) {
        int even = 1;
        int odd = 1;

        int cur = 0;
        do {
            int evenp = evenPalindrome(even);
            int oddp = oddPlaindrome(odd);
            cur = min(evenp, oddp);
            if (evenp < oddp) {
                ++even;
            } else {
                ++odd;
            }
        } while (!(cur >= N && isPrime(cur)));

        return cur;
    }
};




Related Posts

Three Equal Parts Problem

LeetCode 927. You are given an array arr which consists...

Surface Area Of 3D Shapes Problem

LeetCode 892. You are given an n x n grid...

Super Palindromes Problem

LeetCode 906. Let’s say a positive integer is a super-palindrome...

Smallest Range I Problem

LeetCode 908. You are given an integer array nums and...

Projection Area Of 3D Shapes Problem

LeetCode 883. You are given an n x n grid...

Prime Palindrome Problem

LeetCode 866. Given an integer n, return the smallest prime...