ISC Practicals and Theory - Emirp Number

An emirp number, also called a twisted prime, is a prime number that is still a prime when its digits are reversed. This note gives the program written in the main method alone: it reverses the digits, then counts the factors of the number and of its reverse.

Definition

A prime number $N$ has exactly two factors, $1$ and $N$. A number is an emirp number (twisted prime) if $N$ is prime and the number formed by reversing its digits is also prime.

• $13$ is an emirp: $13$ is prime, its reverse $31$ is prime.
• $23$ is not an emirp: $23$ is prime, but its reverse $32$ is not.
• $12$ is not an emirp: $12$ is not prime.
• $11$ is an emirp in this program: $11$ is prime and its reverse $11$ is prime. The program follows the wording "prime, and its reverse is prime". Some books also require the reverse to be a different number, which would leave out $11$, $101$ and other palindromic primes.

Algorithm

1. Accept the number num. If num < 1, display Invalid input and stop.
2. Reverse the digits: copy num into n and set rev = 0. While n > 0, take the last digit d = n % 10, do rev = rev * 10 + d and n = n / 10.
3. Count the factors of num in c1: for i from 1 to num, add 1 to c1 whenever num % i == 0.
4. Count the factors of rev in c2 in the same way.
5. A prime number has exactly two factors. If c1 == 2 and c2 == 2, display that num is an emirp number. Otherwise display that it is not.

Program

Everything is written inside main: one loop reverses the number and two for loops count the factors of the number and of its reverse.

import java.util.Scanner;
public class Emirp
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int num = sc.nextInt();                 // the number to be checked
        if (num < 1)
        {
            System.out.println("Invalid input");
        }
        else
        {
            int n = num, rev = 0;               // rev stores the reverse of num
            while (n > 0)
            {
                int d = n % 10;                 // last digit
                rev = rev * 10 + d;
                n = n / 10;
            }
            int c1 = 0;                         // number of factors of num
            for (int i = 1; i <= num; i++)
            {
                if (num % i == 0)
                    c1++;
            }
            int c2 = 0;                         // number of factors of rev
            for (int i = 1; i <= rev; i++)
            {
                if (rev % i == 0)
                    c2++;
            }
            if (c1 == 2 && c2 == 2)             // a prime has exactly two factors
                System.out.println(num + " is an emirp number");
            else
                System.out.println(num + " is not an emirp number");
        }
    }
}

Variable description table

Sample input and output

Enter a number: 13
13 is an emirp number

Enter a number: 23
23 is not an emirp number

Enter a number: 11
11 is an emirp number

Enter a number: -5
Invalid input

Dry run

Input: num = 13

First the digits of 13 are reversed:

The loop stops because n = 0, so rev = 31.

Then the factors of 13 and of 31 are counted. In each for loop, the remainder is 0 only for $i = 1$ and $i$ equal to the number:

Both conditions are true (c1 == 2 and c2 == 2), so the program shows that $13$ is an emirp number, as in the first sample run.

Variations

1. Range: "Display all emirp numbers between m and n."
2. Recursive technique: "Check whether a number is an emirp number, using a recursive method to reverse the digits."
3. Twin primes: "Display all twin prime pairs in a given range."
4. Palindrome prime: "Check whether a number is a prime whose reverse is the same number."