CREATE OWN LIBRARY

Description

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.