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.
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.
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 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().
The space complexity of this program is O(1) as it requires a constant number of memory spaces to execute the program.