FOR FREE YEAR SOLVED

Emirp Number

Back to Programming

Description

A number is said to be an emirp number if the number is prime and its reverse is also prime

 

For example:

If the number is 113, this number is a prime number; the reverse of the number is 311 which is also a prime number. Hence, 113 is an emirp number.

If we consider a number 23, the number is a prime number. But if we reverse the number, we get 32 which is divisible by 2, 4, 8, 16. Therefore, 32 is not a prime number.   Hence, 23 is not an emirp number.

 

For this program, a number is taken as input from the user. First, the given number is checked for prime. If the number is a prime number then, the reverse of this number is calculated and checked for prime. If the reverse is also a prime number, then the number is said to be an emirp number, otherwise not.

Algorithm

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

Code

Time Complexity:

for(i=1;i<=n;i++)-----------------------------------------------O(n)

                {     if(n%i==0)

                       c++;    }

                //if the number is prime then the reverse should be checked

                if(c==2)--------------------------------------------------------O(1)

                {     //reversing the number

                                while(tmp>0)-----------------------------------O(p) [‘p’ is the number of digits]

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

                                                tmp=tmp/10;   } 

                                //checking if the reverse is also prime or not

                                c=0;

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

                                {       if(m%i==0)

                                         c++;    }

The time complexity of this program is O(m+n+p) where  ‘n’ is the given number, ‘m’ is the reversed number and ‘p’ is the number of digits of the number. 

But for more optimization, we can check from 2 to n to check for prime number because a number ‘n’ can have a maximum 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 number of memory spaces to execute the program.