ISC Practicals and Theory - Prime Number

A prime number is a number that has exactly two factors. This program accepts a number, counts its factors with a loop and tells whether it is prime, all inside main.

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$.
• $1$ is not prime: it has only one factor.

Algorithm

1. Start. Read the number into n.
2. If n < 1, display "Invalid input" and stop.
3. Set count = 0.
4. Repeat for i from $1$ to n:
   • If n % i == 0, i is a factor, so increase count by $1$.
5. If count == 2, display that n is a prime number. Otherwise display that it is not.
6. Stop.

Program

The whole logic is written inside the main method of the class PrimeNumber.

import java.util.Scanner;
public class PrimeNumber
{
    public static void main(String args[])
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter a number: ");
        int n = sc.nextInt();
        if (n < 1)
        {
            System.out.println("Invalid input");
        }
        else
        {
            int count = 0;
            for (int i = 1; i <= n; i++)
            {
                if (n % i == 0)
                    count++;
            }
            if (count == 2)
                System.out.println(n + " is a prime number");
            else
                System.out.println(n + " is not a prime number");
        }
    }
}

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: n = 7

The loop ends with count = 2, so the program displays that $7$ is a prime number, as in the first sample run.

Variations

1. Range: "Display all prime numbers between m and n."
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."