# CREATE OWN LIBRARY

## Check a Prime Palindrome Number

Back to Programming

### Description

A number is said to be a prime palindrome number if the number is a prime number as well as a palindrome.

For example, if we consider a number 101, the number is a prime number as well as a palindrome number.

But if we consider the number 13, then it is a prime number but not a palindrome number. Similarly, if we consider the number 22, then it is a palindrome number but not a prime number.

Here, the number is taken as input. First, it is checked whether the number is a prime number or not. If the number is a prime number then the number is checked for the palindrome, if both the conditions satisfy then the number is a prime palindrome number otherwise not.

### Algorithm

``````INPUT: A number
OUTPUT: Whether the number is a prime palindrome or not
PROCESS:
Step 1: [Taking the input]
Read n [the number to be checked]
Step 2: [Checking for prime palindrome]
Set c<-0
Set rev<-0
Set tmp<-n
[Checking for prime number]
For i=1 to tmp repeat
[Counting the number of factors of the number]
If tmp mod i=0 then
Set c<-c+1
[End of ‘if’]
[End of ‘for’ loop]
[If the number is prime check for palindrome]
If c=2 then
[Reversing the number]
While tmp>0 repeat
Set rev<-rev×10+(tmp mod 10)
Set tmp<-tmp/10
[End of ‘while’ loop]
[Checking for prime palindrome number]
If rev=n then
Print "The given number is a prime palindrome number"
Else
Print "The given number is not a prime palindrome number"
[End of ‘if’]
Else
Print "The given number is not a prime palindrome number"
[End of ‘else’]
Step 3: Stop.
``````

## Time Complexity:

for(i=1;i<=tmp;i++)----------------------------------------O(m)

{     //counting the number of factors of the number

if(tmp%i==0)

c++;  }

//if the number is prime check for palindrome

if(c==2)

{     //reversing the number

while(tmp>0)-------------------------------O(n)

{              rev=rev*10+(tmp%10);

tmp/=10;

}

//checking for prime palindrome number

if(rev==n)

printf("The given number is a prime palindrome number");

else

printf("The given number is not a prime palindrome number");

}

The time complexity of this program is O(m+n) where ‘m’ is the number which is checked to be as prime and ‘n’ is the number of digits of the given number. For the simplicity of the program, the loop to check the prime number is executed from 1 to the number.

But for more optimization, we can check from 2 to $\sqrt{\mathrm{n}}$  because a number ‘n’ can have maximum $\sqrt{\mathrm{n}}$  number of factors. So, we can say the most optimized complexity is O($\sqrt{\mathrm{n}}$).

## Space Complexity:

The space complexity of this program is O(1) as it requires a constant memory space to check for prime palindrome for any given number.