FOR FREE CONTENT

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.

Code

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 n  because a number ‘n’ can have maximum n  number of factors. So, we can say the most optimized complexity is O(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.