Skip to main content

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:

  1. 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).

  2. Reverse the number (13) to get 31.

  3. 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).

  4. 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

  1. 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.

  2. The reverse_num function takes a number and returns its reverse. It uses a while loop to iteratively reverse the digits of the number.

  3. The is_emirp_number function takes a number and checks if it is an emirp number. It does this by calling the is_prime function to check if the number is prime and then calls reverse_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 the is_prime and reverse_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.





Comment

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