FOR FREE CONTENT
Emirp Numbers in a range
Back to ProgrammingDescription
Before seeing the program please follow the previous program Check emirp number
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, the ranges are taken as inputs. Each number between this range (including the lower and the upper limit) 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 displayed as the output.
Algorithm
INPUT: The ranges
OUTPUT: The emirp numbers between these ranges
PROCESS:
Step 1: [Taking the inputs]
Read m, n [the lower limit and the upper limit]
Step 2: [Finding the emirp numbers]
For k=m to n repeat
Set p<-0
Set c<-0
Set tmp<-k
[Checking if the original number is prime or not]
For i=1 to k repeat
If k 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 p<-p×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 p repeat
If p mod i=0 then
Set c<-c+1
[End of ‘if’]
[End of ‘for’ loop]
[Checking for prime number]
If c=2 then
Print k
[End of ‘if’]
[End of ‘if’]
[End of ‘for’ loop]
Step 3: Stop.
Code
Time Complexity:
for(k=m;k<=n;k++)-------------------------------------------O(m)
{ p=0;
c=0;
tmp=k;
//checking if the original number is prime or not
for(i=1;i<=k;i++)----------------------------------O(k)
{ if(k%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(n) [‘n’ is the number of digits]
{
p=p*10+(tmp%10);
tmp=tmp/10; }
//checking if the reverse is also prime or not
c=0;
for(i=1;i<=p;i++)---------------------------------O(p)
{
if(p%i==0)-----------------------------O(1)
c++; }
//checking for prime number
if(c==2)
printf("%d ",k); }
}
The time complexity of this program is O(m*(k+n+p)) where m is the numbers between ranges and ‘k’ is the number to be checked , ‘n’ is the number of digits, ‘p’ is the number after reversing.
But for more optimization we can check from 2 to to check for prime number because a number ‘n’ can have maximum
number of factors. So, we can say most optimized complexity is O().
Space Complexity:
The space complexity of this program is O(1) as it requires a constant number of memory spaces to run the program for any given input.
