Find next palindrome prime in C++

In this problem, we are given an element N. We need to find the next palindrome prime.

Problem Description − We need to find the smallest prime number which is also a palindrome number, greater than N.

Palindrome Number is a number in which the numbers are the same in both directions.

Prime Number is a number if its only factors are 1 and itself.

Let’s take an example to understand the problem,

Input

N = 12

Output

101

Explanation

The series of palindromes greater than 12 are 22, 33, 44, 55, 66, 77, 88, 99, 101… out of these the smallest palindrome is 101.

Solution Approach

A simple solution to the problem is by finding all palindromes greater than N that are primes.

A more efficient solution is by finding the even digit palindrome which is multiple of 11.

Here is a proof of this solution,

11% 11 = 0 1111% 11 = 0

Using this we will find palindrome with even digits −

xyzzyx % 11 = 0, which makes all even number digits not palindrome.

Program to illustrate the working of our solution,

Example

#include <iostream> #include <string> using namespace std; bool isPrime(int num) {    if (num < 2 || num % 2 == 0)       return num == 2;    for (int i = 3; i * i <= num; i += 2)       if (num % i == 0)          return false;    return true; } int primePalindrome(int N) {    if (8 <= N && N <= 11)       return 11;    for (int x = 1; x < 100000; ++x) {       string s = to_string(x), r(s.rbegin(), s.rend());       int y = stoi(s + r.substr(1));       if (y >= N && isPrime(y))          return y;    }    return -1; } int main() {    int N = 432;    cout<<"The next prime palindrome is "<<findNextPrimePallindrome(432);    return 0; }

Output

The next number with same set of digits is 92543