ISC Practicals and Theory - Circular Prime

A circular prime is a prime number that stays prime when its digits are rotated, one place at a time, until every rotation has been seen. This program is written as a class CircularPrime with a data member and separate methods for input, the prime test, the digit count, the rotation check and the display. The main method only creates an object and calls the methods.

Definition

A prime number $N$ is a circular prime if every number formed by rotating its digits is also prime. A rotation moves the last digit to the front.

• $197$ is a circular prime: its rotations $197$, $719$ and $971$ are all prime.
• $193$ is not a circular prime: it is prime, but the rotation $319 = 11 \times 29$ is not.
• $13$ is a circular prime: $13$ and $31$ are both prime.

Algorithm

1. In main, create the object ob of class CircularPrime. The constructor sets num = 0.
2. Call ob.input(), which reads the number into the data member num.
3. Call ob.display():
   • If num < 1, display "Invalid input".
   • Otherwise call isCircularPrime() and display whether num is a circular prime.
4. The method isCircularPrime() works as follows:
   • Call countDigits() to get the number of digits d.
   • Set p to $10^{d-1}$ by multiplying by $10$ exactly d - 1 times.
   • Set r = num.
   • Repeat d times: display the rotation r; if isPrime(r) is false, return false; otherwise form the next rotation using r = (r % 10) * p + r / 10.
   • If every rotation was prime, return true.
5. The method isPrime(n) counts the factors of n by testing every i from $1$ to n. It returns true only if count == 2.
6. The method countDigits() copies num into t and divides it by $10$ until it becomes $0$, counting the divisions.

The rotation works on the last digit and the rest of the number. For $r = 197$ and $p = 100$: r % 10 is $7$ and r / 10 is $19$, so the next rotation is $7 \times 100 + 19 = 719$.

Program

The constructor CircularPrime() initialises num, input() reads the number, isPrime(int n) tests one number, countDigits() counts the digits of num, isCircularPrime() generates and tests each rotation, and display() prints the result.

import java.util.Scanner;
public class CircularPrime
{
    int num;

    CircularPrime()
    {
        num = 0;
    }

    void input()
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        num = sc.nextInt();
    }

    boolean isPrime(int n)
    {
        int count = 0;
        for (int i = 1; i <= n; i++)
        {
            if (n % i == 0)
                count++;
        }
        return count == 2;
    }

    int countDigits()
    {
        int d = 0;
        int t = num;
        while (t > 0)
        {
            d++;
            t = t / 10;
        }
        return d;
    }

    boolean isCircularPrime()
    {
        int d = countDigits();
        int p = 1;
        for (int i = 1; i < d; i++)
            p = p * 10;
        int r = num;
        for (int i = 1; i <= d; i++)
        {
            System.out.println("Rotation " + i + ": " + r);
            if (!isPrime(r))
                return false;
            r = (r % 10) * p + r / 10;
        }
        return true;
    }

    void display()
    {
        if (num < 1)
            System.out.println("Invalid input");
        else if (isCircularPrime())
            System.out.println(num + " is a circular prime");
        else
            System.out.println(num + " is not a circular prime");
    }

    public static void main(String args[])
    {
        CircularPrime ob = new CircularPrime();
        ob.input();
        ob.display();
    }
}

Variable description table

Sample input and output

Enter a number: 197
Rotation 1: 197
Rotation 2: 719
Rotation 3: 971
197 is a circular prime

Enter a number: 193
Rotation 1: 193
Rotation 2: 319
193 is not a circular prime

Enter a number: 13
Rotation 1: 13
Rotation 2: 31
13 is a circular prime

Enter a number: -7
Invalid input

Dry run

Input: num = 193, so d = 3 and p = 100.

isCircularPrime() returns false at the second rotation because $319 = 11 \times 29$ has more than two factors, so display() shows that $193$ is not a circular prime, as in the second sample run.

Variations

1. Recursive technique: "Check whether a number is a circular prime using a recursive method to test for a prime."
2. Range: "Display all circular primes between m and n."
3. Emirp number: "Check whether a number is an emirp number: a prime whose reverse is also prime."
4. Twin primes: "Display all twin prime pairs in a given range."