ISC Practicals and Theory - Prime Number (Recursive Technique)

A prime number is a number that has exactly two factors. In this version the factors are counted by a method that calls itself, instead of a loop.

Definition

A natural number $N$ is a prime number if it has exactly two factors: $1$ and $N$ itself.

• $7$ is prime: its only factors are $1$ and $7$.
• $12$ is not prime: its factors are $1, 2, 3, 4, 6, 12$.

Algorithm

1. In main, create the object ob of class PrimeRec and call input() to read num.
2. Call display(). If num < 1, display "Invalid input".
3. Otherwise call countFactors(1) and check whether it returns $2$.
4. The recursive method countFactors(int i) tests the divisor i:
   • Base case: if i > num, return $0$, since there are no more divisors to test.
   • Recursive case: if num % i == 0, return $1$ + countFactors(i + 1).
   • Otherwise return countFactors(i + 1).
5. If the count is $2$, display that num is a prime number, else display that it is not.

Program

The method countFactors(int i) calls itself with the next divisor until i crosses num.

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

    PrimeRec()
    {
        num = 0;
    }

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

    int countFactors(int i)
    {
        if (i > num)
            return 0;
        if (num % i == 0)
            return 1 + countFactors(i + 1);
        return countFactors(i + 1);
    }

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

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

Variable description table

Sample input and output

Enter a number: 7
7 is a prime number

Enter a number: 12
12 is not a prime number

Enter a number: 1
1 is not a prime number

Enter a number: -4
Invalid input

Dry run

Input: num = 7. The calls are made in this order, and each returns its value on the way back.

Returning back: countFactors(7) gives $1 + 0 = 1$, and countFactors(1) gives $1 + 1 = 2$. The count is $2$, so $7$ is a prime number, as in the first sample run.

Variations

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