Prime Number Program in Java

Write a Java program to check if a given number is a Prime number. If the number is Prime, then display it is a prime number else display it is not a prime number.

What is Prime Number in Java?

A prime number is a natural number that is greater than 1 and is only divisible by 1 and itself. In other words, no number except the number itself, and 1 can divide a prime number.

Example: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 …., etc.

There are several ways to write a prime number program in Java language. Let’s look at all the different techniques to write a prime number program.

• Prime Number Program in Java using For Loop
• Prime Number Program in Java using While Loop
• Java Program to Find Prime Numbers in a Given Range

In this method, we enter any integer as an input you want to check for and we use modulos operation along with loops and if else conditions to get the desired output.

Here is the source code of the Java Program to Check if a Given Number is Prime Number or not using for loop. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

/*
 * Java Program to Check Whether a Number is Prime or not using For Loop
 */
 
import java.util.Scanner;
public class CheckPrime
{
    public static void main(String args[])
    {       
        int j, num, flag = 0;
        System.out.print("Enter the number :");
        Scanner s = new Scanner(System.in);
        num = s.nextInt();
        for( j = 2; j < num; j++)
        {
            if(num % j == 0)
            {
                flag = 0;
                break;
            }
            else
            {
                flag = 1;
            }
         }
         if(flag == 1)
         {
             System.out.println(""+num+" is a prime number.");
         }
         else
         {
             System.out.println(""+num+" is not a prime number.");
         }           
    }
}

1. Take a number as input and store it in the variable num.
2. If the number is lesser than or equal to 1, then print the output as “It is not a prime number“.
3. Initialize the variable flag to zero.
4. Using for loop, check if the input number is divisible by any of the natural numbers starting from the digit 2.
5. If it is, then assigns the variable flag with 1.
6. Print the output as “It is a prime number“, if the variable flag==1.
7. Otherwise print the output as “It is not a prime number” and exit.

Time Complexity: O(n)
The above program for checking whether a number is prime or not has a time complexity of O(n/2) = O(n) as the loop runs from 2 to n/2, where n is the number given as input.

Space Complexity: O(1)
In this program we are not initializing any array or other data types that takes lot of storage. We are just initializing the variable. Therefore, our space complexity is constant, i.e. O(1).

Testcase 1: In this case, we enter the number “7” as input to check whether it is a prime number or not.

Enter a number:
7
7 is a prime number

Testcase 2: In this case, we enter the number “12” as input to check whether it is a prime number or not.

Enter a number:
12
12 is not a prime number

In this method, we enter any integer as an input you want to check for and we use modulos operation along with loops and if else conditions to get the desired output.

Here is the source code of the Java Program to Check if a Given Number is Prime Number or not using for loop. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

import java.util.Scanner;
public class Checkprime
{
    public static void main(String[] args)
    {
        int i = 1, num, flag=0;
        System.out.print("Enter the number :");
        Scanner s = new Scanner(System.in);
        num = s.nextInt();
        if (num <= 1)
        {
            System.out.println("The number is not prime");
            return;
        }
        while (i <= num / 2)
        {
            if (num % i == 0)
            {
                flag++;
            }
            i++;
        }
        if (flag > 1)
        {
            System.out.println(""+num+" is not a prime number.");
        }
        else
        {
            System.out.println(""+num+" is a prime number.");
        }
   }
}

1. Take a number as input and store it in the variable num.
2. If the number is lesser than or equal to 1, then print the output as “The number is not prime“.
3. Initializes a while loop that runs as long as i is less than or equal to half of num.
4. Checks if num is divisible by i, and if so, increments the flag variable.
5. Increments the i variable and checks if the flag variable is greater than 1, and if so, prints the message “num is not a prime number.”
6. If the flag variable is less than or equal to 1, prints the message “num is a prime number.”

Testcase 1: In this case, we enter the number “13” as input to check whether it is a prime number or not.

Enter a number:
13
13 is a prime number

Testcase 2: In this case, we enter the number “16” as input to check whether it is a prime number or not.

Enter a number:
16
16 is not a prime number

In this approach, we enter the upper and lower limits as input. And we use modulus operation along with double for loops and if-else conditions to get the output.

Here is the source code of the Java Program to Find Prime Numbers Within a Range of n1 and n2. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

import java.util.Scanner;
public class Prime
{
    public static void main(String args[])
    {
         int s1, s2, s3, flag = 0, i, j;
         Scanner s = new Scanner(System.in);
         System.out.println ("Enter the lower limit :"); 
         s1 = s.nextInt();
         System.out.println ("Enter the upper limit :"); 
         s2 = s.nextInt();
         System.out.println ("The prime numbers in between the entered limits are :");
         for(i = s1; i <= s2; i++)
         {
             for( j = 2; j < i; j++)
             {
                 if(i % j == 0)
                 {
                     flag = 0;
                     break;
                 }
                 else
                 {
                     flag = 1;
                 }
             }
             if(flag == 1)
             {
                 System.out.println(i);
             }
         }
    }
}

1. The program asks the user to input two numbers and store it in s1 and s2 variables.
2. It checks all the numbers between these two numbers to find prime numbers.
3. A prime number is a number that is only divisible by 1 and itself.
4. To check if a number is prime, the program divides it by all the numbers between 2 and the number itself minus 1.
5. If the number is only divisible by 1 and itself, it’s a prime number and is printed to the console.

$ javac Prime.java
$ java Prime
 
Enter the lower limit :
2
Enter the upper limit :
20
The prime numbers in between the entered limits are :
3
5
7
11
13
17
19

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.