## 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.
``````

## 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 $\sqrt{\mathrm{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($\sqrt{\mathrm{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.