Check if given number is emirp number or not
In number theory, an emirp (prime spelled backward) is a prime number that yields a different prime number when its decimal digits are reversed. For example, 13 is a prime number, and its reverse is 31, which is also prime. Hence, 13 is an emirp number.
The goal of this problem is to determine whether a given number is an emirp number or not. To do this, we need to check if the given number is prime and if its reverse is also prime.
Explanation with Suitable Example
Let's take the number 13 as an example to illustrate the process:
-
Check if the number (13) is prime. To do this, we apply the
is_prime
function, which checks if the number is divisible by any number other than 1 and itself. In this case, 13 is a prime number, and the function returns true (1). -
Reverse the number (13) to get 31.
-
Check if the reversed number (31) is prime. Again, we use the
is_prime
function to check for primality. 31 is also a prime number, so the function returns true (1). -
Since both the original number (13) and its reverse (31) are prime, we can conclude that 13 is an emirp number.
Pseudocode
function is_prime(number):
if number is 2 or 3 or 5:
return true
if number is less than or equal to 1 or number is divisible by 2 or 3 or 5:
return false
i = 11
while (i * i) is less than or equal to number:
if number is divisible by i or i + 2:
return false
i += 6
return true
function reverse_num(number):
reversed = 0
while number is not 0:
reversed = reversed * 10 + (number % 10)
number = number / 10
return reversed
function is_emirp_number(number):
if is_prime(number) and is_prime(reverse_num(number)):
print(number, "is an Emirp Number")
else:
print(number, "is not an Emirp Number")
Algorithm Explanation
-
The
is_prime
function checks if the given number is prime using a fast prime-checking algorithm. It handles special cases for numbers 2, 3, and 5 and then checks for divisibility by 2, 3, and 5. After that, it uses a loop with increments of 6 to efficiently check for divisibility by other numbers up to the square root of the given number. -
The
reverse_num
function takes a number and returns its reverse. It uses a while loop to iteratively reverse the digits of the number. -
The
is_emirp_number
function takes a number and checks if it is an emirp number. It does this by calling theis_prime
function to check if the number is prime and then callsreverse_num
to get the reversed number and checks its primality as well. If both the number and its reverse are prime, it prints that the number is an emirp number; otherwise, it prints that it is not.
Code Solution
Here given code implementation process.
// C program
// Check if given number is emirp number or not
#include <stdio.h>
//Check that whether given number is prime or not
int is_prime(int number)
{
if (number == 2 || number == 3 || number == 5)
{
// Base case
return 1;
}
else if (number <= 1 || (number % 2 == 0) || (number % 3 == 0) || (number % 5 == 0))
{
//When number is divisible by (2,3,5) or less than 2
return 0;
}
int i = 11;
while ((i * i) <= number)
{
if (number % i == 0)
{
//When number is divisible of current i value
return 0;
}
else if (number % (i + 2) == 0)
{
//When number is divisible of current i + 2 value
return 0;
}
i = i + 6;
}
return 1;
}
int reverse_num(int number)
{
int result = 0;
while (number != 0)
{
result = result * 10 + (number % 10);
number = number / 10;
}
//returning the reversal of number
return result;
}
void is_emirp_number(int number)
{
if (is_prime(number) && is_prime(reverse_num(number)))
{
//When given number is prime
//And its reverse is also a prime number
printf("\n [%d] Is Emirp Number", number);
}
else
{
printf("\n [%d] Is Not Emirp Number", number);
}
}
int main()
{
//Test case
is_emirp_number(13);
is_emirp_number(12);
is_emirp_number(1091);
is_emirp_number(131);
is_emirp_number(123);
is_emirp_number(149);
is_emirp_number(143);
is_emirp_number(157);
return 0;
}
Output
[13] Is Emirp Number
[12] Is Not Emirp Number
[1091] Is Emirp Number
[131] Is Emirp Number
[123] Is Not Emirp Number
[149] Is Emirp Number
[143] Is Not Emirp Number
[157] Is Emirp Number
/*
Java program
Check if given number is emirp number or not
*/
class EmirpNumber
{
//Check that whether given number is prime or not
public boolean is_prime(int number)
{
if (number == 2 || number == 3 || number == 5)
{
// Base case
return true;
}
else if (number <= 1 || (number % 2 == 0) || (number % 3 == 0) || (number % 5 == 0))
{
//When number is divisible by (2,3,5) or less than 2
return false;
}
int i = 11;
while ((i * i) <= number)
{
if (number % i == 0)
{
//When number is divisible of current i value
return false;
}
else if (number % (i + 2) == 0)
{
//When number is divisible of current i + 2 value
return false;
}
i = i + 6;
}
return true;
}
public int reverse_num(int number)
{
int result = 0;
while (number != 0)
{
result = result * 10 + (number % 10);
number = number / 10;
}
//returning the reversal of number
return result;
}
public void is_emirp_number(int number)
{
if (is_prime(number) && is_prime(reverse_num(number)))
{
//When given number is prime
//And its reverse is also a prime number
System.out.print("\n [" + number + "] Is Emirp Number");
}
else
{
System.out.print("\n [" + number + "] Is Not Emirp Number");
}
}
public static void main(String[] args)
{
EmirpNumber obj = new EmirpNumber();
//Test case
obj.is_emirp_number(13);
obj.is_emirp_number(12);
obj.is_emirp_number(1091);
obj.is_emirp_number(131);
obj.is_emirp_number(123);
obj.is_emirp_number(149);
obj.is_emirp_number(143);
obj.is_emirp_number(157);
}
}
Output
[13] Is Emirp Number
[12] Is Not Emirp Number
[1091] Is Emirp Number
[131] Is Emirp Number
[123] Is Not Emirp Number
[149] Is Emirp Number
[143] Is Not Emirp Number
[157] Is Emirp Number
//Include header file
#include <iostream>
using namespace std;
/*
C++ program
Check if given number is emirp number or not
*/
class EmirpNumber
{
public:
//Check that whether given number is prime or not
bool is_prime(int number)
{
if (number == 2 || number == 3 || number == 5)
{
// Base case
return true;
}
else if (number <= 1 || (number % 2 == 0) || (number % 3 == 0) || (number % 5 == 0))
{
//When number is divisible by (2,3,5) or less than 2
return false;
}
int i = 11;
while ((i *i) <= number)
{
if (number % i == 0)
{
//When number is divisible of current i value
return false;
}
else if (number % (i + 2) == 0)
{
//When number is divisible of current i + 2 value
return false;
}
i = i + 6;
}
return true;
}
int reverse_num(int number)
{
int result = 0;
while (number != 0)
{
result = result *10 + (number % 10);
number = number / 10;
}
//returning the reversal of number
return result;
}
void is_emirp_number(int number)
{
if (this->is_prime(number) && this->is_prime(this->reverse_num(number)))
{
//When given number is prime
//And its reverse is also a prime number
cout << "\n [" << number << "] Is Emirp Number";
}
else
{
cout << "\n [" << number << "] Is Not Emirp Number";
}
}
};
int main()
{
EmirpNumber obj = EmirpNumber();
//Test case
obj.is_emirp_number(13);
obj.is_emirp_number(12);
obj.is_emirp_number(1091);
obj.is_emirp_number(131);
obj.is_emirp_number(123);
obj.is_emirp_number(149);
obj.is_emirp_number(143);
obj.is_emirp_number(157);
return 0;
}
Output
[13] Is Emirp Number
[12] Is Not Emirp Number
[1091] Is Emirp Number
[131] Is Emirp Number
[123] Is Not Emirp Number
[149] Is Emirp Number
[143] Is Not Emirp Number
[157] Is Emirp Number
//Include namespace system
using System;
/*
C# program
Check if given number is emirp number or not
*/
class EmirpNumber
{
//Check that whether given number is prime or not
public Boolean is_prime(int number)
{
if (number == 2 || number == 3 || number == 5)
{
// Base case
return true;
}
else if (number <= 1 || (number % 2 == 0) || (number % 3 == 0) || (number % 5 == 0))
{
//When number is divisible by (2,3,5) or less than 2
return false;
}
int i = 11;
while ((i * i) <= number)
{
if (number % i == 0)
{
//When number is divisible of current i value
return false;
}
else if (number % (i + 2) == 0)
{
//When number is divisible of current i + 2 value
return false;
}
i = i + 6;
}
return true;
}
public int reverse_num(int number)
{
int result = 0;
while (number != 0)
{
result = result * 10 + (number % 10);
number = number / 10;
}
//returning the reversal of number
return result;
}
public void is_emirp_number(int number)
{
if (is_prime(number) && is_prime(reverse_num(number)))
{
//When given number is prime
//And its reverse is also a prime number
Console.Write("\n [" + number + "] Is Emirp Number");
}
else
{
Console.Write("\n [" + number + "] Is Not Emirp Number");
}
}
public static void Main(String[] args)
{
EmirpNumber obj = new EmirpNumber();
//Test case
obj.is_emirp_number(13);
obj.is_emirp_number(12);
obj.is_emirp_number(1091);
obj.is_emirp_number(131);
obj.is_emirp_number(123);
obj.is_emirp_number(149);
obj.is_emirp_number(143);
obj.is_emirp_number(157);
}
}
Output
[13] Is Emirp Number
[12] Is Not Emirp Number
[1091] Is Emirp Number
[131] Is Emirp Number
[123] Is Not Emirp Number
[149] Is Emirp Number
[143] Is Not Emirp Number
[157] Is Emirp Number
<?php
/*
Php program
Check if given number is emirp number or not
*/
class EmirpNumber
{
//Check that whether given number is prime or not
public function is_prime($number)
{
if ($number == 2 || $number == 3 || $number == 5)
{
// Base case
return true;
}
else if ($number <= 1 || ($number % 2 == 0) || ($number % 3 == 0) || ($number % 5 == 0))
{
//When number is divisible by (2,3,5) or less than 2
return false;
}
$i = 11;
while (($i * $i) <= $number)
{
if ($number % $i == 0)
{
//When number is divisible of current i value
return false;
}
else if ($number % ($i + 2) == 0)
{
//When number is divisible of current i + 2 value
return false;
}
$i = $i + 6;
}
return true;
}
public function reverse_num($number)
{
$result = 0;
while ($number != 0)
{
$result = $result * 10 + ($number % 10);
$number = intval($number / 10);
}
//returning the reversal of number
return $result;
}
public function is_emirp_number($number)
{
if ($this->is_prime($number) && $this->is_prime($this->reverse_num($number)))
{
//When given number is prime
//And its reverse is also a prime number
echo "\n [". $number ."] Is Emirp Number";
}
else
{
echo "\n [". $number ."] Is Not Emirp Number";
}
}
}
function main()
{
$obj = new EmirpNumber();
//Test case
$obj->is_emirp_number(13);
$obj->is_emirp_number(12);
$obj->is_emirp_number(1091);
$obj->is_emirp_number(131);
$obj->is_emirp_number(123);
$obj->is_emirp_number(149);
$obj->is_emirp_number(143);
$obj->is_emirp_number(157);
}
main();
Output
[13] Is Emirp Number
[12] Is Not Emirp Number
[1091] Is Emirp Number
[131] Is Emirp Number
[123] Is Not Emirp Number
[149] Is Emirp Number
[143] Is Not Emirp Number
[157] Is Emirp Number
/*
Node Js program
Check if given number is emirp number or not
*/
class EmirpNumber
{
//Check that whether given number is prime or not
is_prime(number)
{
if (number == 2 || number == 3 || number == 5)
{
// Base case
return true;
}
else if (number <= 1 || (number % 2 == 0) || (number % 3 == 0) || (number % 5 == 0))
{
//When number is divisible by (2,3,5) or less than 2
return false;
}
var i = 11;
while ((i * i) <= number)
{
if (number % i == 0)
{
//When number is divisible of current i value
return false;
}
else if (number % (i + 2) == 0)
{
//When number is divisible of current i + 2 value
return false;
}
i = i + 6;
}
return true;
}
reverse_num(number)
{
var result = 0;
while (number != 0)
{
result = result * 10 + (number % 10);
number = parseInt(number / 10);
}
//returning the reversal of number
return result;
}
is_emirp_number(number)
{
if (this.is_prime(number) && this.is_prime(this.reverse_num(number)))
{
//When given number is prime
//And its reverse is also a prime number
process.stdout.write("\n [" + number + "] Is Emirp Number");
}
else
{
process.stdout.write("\n [" + number + "] Is Not Emirp Number");
}
}
}
function main()
{
var obj = new EmirpNumber();
//Test case
obj.is_emirp_number(13);
obj.is_emirp_number(12);
obj.is_emirp_number(1091);
obj.is_emirp_number(131);
obj.is_emirp_number(123);
obj.is_emirp_number(149);
obj.is_emirp_number(143);
obj.is_emirp_number(157);
}
main();
Output
[13] Is Emirp Number
[12] Is Not Emirp Number
[1091] Is Emirp Number
[131] Is Emirp Number
[123] Is Not Emirp Number
[149] Is Emirp Number
[143] Is Not Emirp Number
[157] Is Emirp Number
# Python 3 program
# Check if given number is emirp number or not
class EmirpNumber :
# Check that whether given number is prime or not
def is_prime(self, number) :
if (number == 2 or number == 3 or number == 5) :
# Base case
return True
elif(number <= 1 or(number % 2 == 0) or(number % 3 == 0) or(number % 5 == 0)) :
# When number is divisible by (2,3,5) or less than 2
return False
i = 11
while ((i * i) <= number) :
if (number % i == 0) :
# When number is divisible of current i value
return False
elif(number % (i + 2) == 0) :
# When number is divisible of current i + 2 value
return False
i = i + 6
return True
def reverse_num(self, number) :
result = 0
while (number != 0) :
result = result * 10 + (number % 10)
number = int(number / 10)
# returning the reversal of number
return result
def is_emirp_number(self, number) :
if (self.is_prime(number) and self.is_prime(self.reverse_num(number))) :
# When given number is prime
# And its reverse is also a prime number
print("\n [", number ,"] Is Emirp Number", end = "")
else :
print("\n [", number ,"] Is Not Emirp Number", end = "")
def main() :
obj = EmirpNumber()
# Test case
obj.is_emirp_number(13)
obj.is_emirp_number(12)
obj.is_emirp_number(1091)
obj.is_emirp_number(131)
obj.is_emirp_number(123)
obj.is_emirp_number(149)
obj.is_emirp_number(143)
obj.is_emirp_number(157)
if __name__ == "__main__": main()
Output
[ 13 ] Is Emirp Number
[ 12 ] Is Not Emirp Number
[ 1091 ] Is Emirp Number
[ 131 ] Is Emirp Number
[ 123 ] Is Not Emirp Number
[ 149 ] Is Emirp Number
[ 143 ] Is Not Emirp Number
[ 157 ] Is Emirp Number
# Ruby program
# Check if given number is emirp number or not
class EmirpNumber
# Check that whether given number is prime or not
def is_prime(number)
if (number == 2 || number == 3 || number == 5)
# Base case
return true
elsif(number <= 1 || (number % 2 == 0) || (number % 3 == 0) || (number % 5 == 0))
# When number is divisible by (2,3,5) or less than 2
return false
end
i = 11
while ((i * i) <= number)
if (number % i == 0)
# When number is divisible of current i value
return false
elsif(number % (i + 2) == 0)
# When number is divisible of current i + 2 value
return false
end
i = i + 6
end
return true
end
def reverse_num(number)
result = 0
while (number != 0)
result = result * 10 + (number % 10)
number = number / 10
end
# returning the reversal of number
return result
end
def is_emirp_number(number)
if (self.is_prime(number) && self.is_prime(self.reverse_num(number)))
# When given number is prime
# And its reverse is also a prime number
print("\n [", number ,"] Is Emirp Number")
else
print("\n [", number ,"] Is Not Emirp Number")
end
end
end
def main()
obj = EmirpNumber.new()
# Test case
obj.is_emirp_number(13)
obj.is_emirp_number(12)
obj.is_emirp_number(1091)
obj.is_emirp_number(131)
obj.is_emirp_number(123)
obj.is_emirp_number(149)
obj.is_emirp_number(143)
obj.is_emirp_number(157)
end
main()
Output
[13] Is Emirp Number
[12] Is Not Emirp Number
[1091] Is Emirp Number
[131] Is Emirp Number
[123] Is Not Emirp Number
[149] Is Emirp Number
[143] Is Not Emirp Number
[157] Is Emirp Number
/*
Scala program
Check if given number is emirp number or not
*/
class EmirpNumber
{
//Check that whether given number is prime or not
def is_prime(number: Int): Boolean = {
if (number == 2 || number == 3 || number == 5)
{
// Base case
return true;
}
else if (number <= 1 || (number % 2 == 0) || (number % 3 == 0) || (number % 5 == 0))
{
//When number is divisible by (2,3,5) or less than 2
return false;
}
var i: Int = 11;
while ((i * i) <= number)
{
if (number % i == 0)
{
//When number is divisible of current i value
return false;
}
else if (number % (i + 2) == 0)
{
//When number is divisible of current i + 2 value
return false;
}
i = i + 6;
}
return true;
}
def reverse_num(n: Int): Int = {
var result: Int = 0;
var number: Int = n;
while (number != 0)
{
result = result * 10 + (number % 10);
number = (number / 10).toInt;
}
//returning the reversal of number
return result;
}
def is_emirp_number(number: Int): Unit = {
if (is_prime(number) && is_prime(reverse_num(number)))
{
//When given number is prime
//And its reverse is also a prime number
print("\n [" + number + "] Is Emirp Number");
}
else
{
print("\n [" + number + "] Is Not Emirp Number");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: EmirpNumber = new EmirpNumber();
//Test case
obj.is_emirp_number(13);
obj.is_emirp_number(12);
obj.is_emirp_number(1091);
obj.is_emirp_number(131);
obj.is_emirp_number(123);
obj.is_emirp_number(149);
obj.is_emirp_number(143);
obj.is_emirp_number(157);
}
}
Output
[13] Is Emirp Number
[12] Is Not Emirp Number
[1091] Is Emirp Number
[131] Is Emirp Number
[123] Is Not Emirp Number
[149] Is Emirp Number
[143] Is Not Emirp Number
[157] Is Emirp Number
/*
Swift 4 program
Check if given number is emirp number or not
*/
class EmirpNumber
{
//Check that whether given number is prime or not
func is_prime(_ number: Int) -> Bool
{
if (number == 2 || number == 3 || number == 5)
{
// Base case
return true;
}
else if (number <= 1 || (number % 2 == 0) || (number % 3 == 0) || (number % 5 == 0))
{
//When number is divisible by (2,3,5) or less than 2
return false;
}
var i: Int = 11;
while ((i * i) <= number)
{
if (number % i == 0)
{
//When number is divisible of current i value
return false;
}
else if (number % (i + 2) == 0)
{
//When number is divisible of current i + 2 value
return false;
}
i = i + 6;
}
return true;
}
func reverse_num(_ n : Int) -> Int
{
var result: Int = 0;
var number: Int = n;
while (number != 0)
{
result = result * 10 + (number % 10);
number = number / 10;
}
//returning the reversal of number
return result;
}
func is_emirp_number(_ number: Int)
{
if (self.is_prime(number) && self.is_prime(self.reverse_num(number)))
{
//When given number is prime
//And its reverse is also a prime number
print("\n [", number ,"] Is Emirp Number", terminator: "");
}
else
{
print("\n [", number ,"] Is Not Emirp Number", terminator: "");
}
}
}
func main()
{
let obj: EmirpNumber = EmirpNumber();
//Test case
obj.is_emirp_number(13);
obj.is_emirp_number(12);
obj.is_emirp_number(1091);
obj.is_emirp_number(131);
obj.is_emirp_number(123);
obj.is_emirp_number(149);
obj.is_emirp_number(143);
obj.is_emirp_number(157);
}
main();
Output
[ 13 ] Is Emirp Number
[ 12 ] Is Not Emirp Number
[ 1091 ] Is Emirp Number
[ 131 ] Is Emirp Number
[ 123 ] Is Not Emirp Number
[ 149 ] Is Emirp Number
[ 143 ] Is Not Emirp Number
[ 157 ] Is Emirp Number
Time Complexity
- The
is_prime
function has a time complexity of approximately O(sqrt(n)), where n is the input number. This is because it iterates up to the square root of the number to check for divisibility. - The
reverse_num
function has a time complexity of O(d), where d is the number of digits in the input number. - The
is_emirp_number
function simply calls theis_prime
andreverse_num
functions, so its time complexity is determined by the time complexity of those functions, which is O(sqrt(n)) and O(d) respectively.
Overall, the time complexity of the entire code is dominated by the is_prime
function, making it
approximately O(sqrt(n)) for each number being checked in the input.
Output Explanation
The given code executes the is_emirp_number
function for multiple test cases and prints whether each
number is an emirp number or not. The output is self-explanatory, indicating which numbers are emirp numbers and
which are not based on their prime properties and the primality of their reversals.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment