Palindromic Primes - GeeksforGeeks

Palindromic Primes - GeeksforGeeks
A palindromic prime (sometimes called a palprime) is a prime number that is also a palindromic number.
Given a number n, print all palindromic primes smaller than or equal to n. For example, If n is 10, the output should be "2, 3, 5, 7′. And if n is 20, the output should be "2, 3, 5, 7, 11′.

bool isPalUtil(int num, int* dupNum)

{

    // Base case (needed for recursion termination):

    // This statement/ mainly compares the first

    // digit with the last digit

    if (oneDigit(num))

        return (num == (*dupNum) % 10);

 

    // This is the key line in this method. Note

    // that all recursive/ calls have a separate

    // copy of num, but they all share same copy

    // of *dupNum. We divide num while moving up

    // the recursion tree

    if (!isPalUtil(num/10, dupNum))

        return false;

 

    // The following statements are executed when

    // we move up the recursion call tree

    *dupNum /= 10;

 

    // At this point, if num%10 contains i'th

    // digit from beiginning, then (*dupNum)%10

    // contains i'th digit from end

    return (num % 10 == (*dupNum) % 10);

}

 

// The main function that uses recursive function

// isPalUtil() to find out whether num is palindrome

// or not

int isPal(int num)

{

    // If num is negative, make it positive

    if (num < 0)

       num = -num;

 

    // Create a separate copy of num, so that

    // modifications made to address dupNum don't

    // change the input number.

    int *dupNum = new int(num); // *dupNum = num

 

    return isPalUtil(num, dupNum);

}

 

// Function to generate all primes and checking

// whether number is palindromic or not

void printPalPrimesLessThanN(int n)

{

    // Create a boolean array "prime[0..n]" and

    // initialize all entries it as true. A value

    // in prime[i] will finally be false if i is

    // Not a prime, else true.

    bool prime[n+1];

    memset(prime, true, sizeof(prime));

 

    for (int p=2; p*p<=n; p++)

    {

        // If prime[p] is not changed, then it is

        // a prime

        if (prime[p] == true)

        {

            // Update all multiples of p

            for (int i=p*2; i<=n; i += p)

                prime[i] = false;

        }

    }

 

    // Print all palindromic prime numbers

    for (int p=2; p<=n; p++)

 

       // checking whether the given number is

       // prime palindromic or not

       if (prime[p] && isPal(p))

          cout << p << " ";

}

Read full article from Palindromic Primes - GeeksforGeeks