FOR FREE MATERIALS

Prime Palindrome Number between a range

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 ranges are taken as input. For each number between the ranges, 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: The ranges
OUTPUT: The prime palindrome numbers between the range
PROCESS:
Step 1: [Taking the inputs]
	Read m, n [the ranges]
Step 2: [Finding the prime palindromes]
	For num=m to n repeat 
Set c<-0
		Set rev<-0
		Set tmp<-num
		[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=num then
				Print num
		[End of ‘if’]
	[End of ‘for’ loop]
Step 3: Stop.

Code

Time Complexity:

for(num=m;num<=n;num++)------------------------------O(p)

{ tmp=num;

c=0;

rev=0;

//checking for prime number

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

{ //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==num)

printf("%d ",num); }

}

The time complexity of this program is O(p*(k+n)) where ‘p’ is the numbers between the ranges, ‘k’ is the number which is checked to be as prime and ‘n’ is the number of digits of the given number.

But for more optimization, we can check from 2 to $\sqrt{n}$ because a number ‘n’ can have maximum $\sqrt{n}$ number of factors. So, we can say the most optimized complexity is O( $\sqrt{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.

Please Login to Bookmark