Prime Number Program in Java

June 29, 2023

Check Whether a Given Number is Prime or Not in Java

Given an integer input greater than 0. The objective is to Check Whether or Not the Number is a Prime. To do so we’ll write a code to Check Whether a Given Number is Prime or Not in Java that checks for the factors of the Number besides 1 and the number itself.

Example
Input : 23
Output : Prime
prime or not in java

Write a program to check if a given number is prime or not in java

Given an integer input, the objective is to – Write a program to check if a given number is prime or not in Java. Here are some of the Methods to Check for Prime –

  • Method 1: Simple iterative solution
  • Method 2: Optimization by break condition
  • Method 3: Optimization by n/2 iterations
  • Method 4: Optimization by √n
  • Method 5: Optimization by skipping even iteration
  • Method 6: Basic Recursion technique

We’ll discuss the above-mentioned methods in detail in the sections below. Check out the Blue box mentioned below to know more about prime numbers.

Prime No Program in Java

Method 1: Simple iterative solution

Working

In this method, we’ll iterate through all the numbers that lay in the interval [1, number] and check if any of them is a factor of the number, if so it’s not a Prime.

For a given integer input we check for the following,

  • If the count of factors for this number is > 2 then
  • It’s not prime else it’s prime
  • A prime number must only be divisible by 1 and the number itself.

Java Code

Run 
// Time Complexity : O(N)
// Space Complexity : O(1)
public class Main
{
  public static void main (String[]args)
  {
    int n = 23;
      checkPrime (n);
  }

  private static void checkPrime (int n)
  {
    int count = 0;

    // negative numbers, 0 and 1 are not prime
    if (n < 2)
      {
	System.out.println ("The given is number " + n + " is not prime");
	System.exit (0);
      }
    // checking the number of divisors b/w [1, n]
    for (int i = 1; i <= n; i++)
      {
	if (n % i == 0)
	  count += 1;
      }

    // if count of divisors greater than 2 then its not prime 
    if (count > 2)
      System.out.println ("The given is number " + n + " is not prime");

    else
      System.out.println ("The given is number " + n + " is prime");
  }
}

Output

23 is : Prime

Greatest of the Three numbers

Leap year or not

Prime number within a given range

Sum of digits of a number

Reverse of a number

Method 2: Optimization by break condition

Working

In the above mentioned we’ll divide the whole loop situation into two parts, we’ll check if the number is lesser than 2, it’s not a prime. It also mustn’t have factors between range [2, num-1]

For an integer input, we check the following,

  • If the number is lesser than 2.
  • If the number has any factors other than 1 and itself.
  • If either of the above two conditions are satisfied, the number is not a Prime.

Java Code

Run

// Write a java program to check whether a given number is prime or not
public class Main
 {
   public static void main (String[]args)
   {

     int i, n = 13;
     boolean isprime = true;

     // 0 and 1 are not prime numbers also, negative numbers are not prime
     if (n < 2)
       {
          isprime = false;
       }
     else
       {
          for (i = 2; i < n; i++)
           {
            if (n % i == 0)
             {
              isprime = false;
                  break;
                }
        }
       }

     String result = isprime ? "Prime" : "not Prime";
     System.out.println ("The number " + n + " is : " + result);

     // Time Complexity : O(N)
     // Space Complexity : O(1)
     // This program is better than previous version as :
     // Condition for 0, 1 and negative numbers checked earlier
     // Loops runs b/w [2, n-1] rather than [1, n]

   }
 }

Output

 13 is : Prime

Method 3: Optimization by n/2 iterations

Working

In this method, we’ll only run the loop until number/2.

As it’s known that the smallest factor of every number if any, will lie in the interval [2, number/2].

For an integer input, we do the following –

  • Check if the number is lesser than 2.
  • Check if the number has any factors other than 1 and the number itself in the interval [2, number/2].
  • If either if the conditions are satisfied, the number is not a Prime.

Java Code

Run 
// Prime no Program in Java
public class Main
 {
   public static void main (String[]args)
   {

     int i,n = 33;
     boolean isprime= true;

     // 0 and 1 are not prime numbers also, negative numbers are not prime
     if(n < 2)
     {
         isprime = false;
     }
     else
     {
     // running loop till n is wasteful because for any number n the numbers in
     // the range(n/2 + 1, n) won't be divisible anyways.
         for(i=2; i <= n/2; i++)
         {
             if(n % i == 0)
             {
                 isprime = false;
                 break;
             }
         }
     }

     String result = isprime ? "Prime" : "not Prime";
     System.out.println ("The number " + n + " is : " + result);

     // Time Complexity : O(N)
     // Space Complexity : O(1)
     // This program is better than previous version as :
     // Loops runs b/w [2, n/2] rather than [2, n-1]


   }
 }

Output

 33 is : Not Prime

Method 4: Optimization by √n

Working

In this method we’ll use for loop to iterate from 2  to square root of the number as it’s known that all the factors of the number lay in the interval [2, sqrt(number)].

For an integer input number, we check,

  • If the number is lesser than 2.
  • If the number has factors other than 1 and the number itself in the interval [2, sqrt(number)].
  • If either of the conditions are satisfied, the number is not a Prime.

Java Code

Run 
public class Main
 {
   public static void main (String[]args)
   {

      int i,n = 29;
     boolean isprime= true;

     // 0 and 1 are not prime numbers also, negative numbers are not prime
     if(n < 2)
     {
         isprime = false;
     }
     else
     {
     // If a number n is not a prime, it can be factored into two factors a and b:
     // n = a * b

     /*Now a and b can't be both greater than the square root of n, 
     since then the product a * b would be greater than sqrt(n) * sqrt(n) = n.
     So in any factorization of n, at least one of the factors must be smaller 
     than the square root of n, and if we can't find any factors less than or equal to 
     the square root, n must be a prime.*/
         for(i=2; i <= Math.sqrt(n); i++)
         {
             if(n % i == 0)
             {
                 isprime = false;
                 break;
             }
         }
     }

     String result = isprime ? "Prime" : "not Prime";
     System.out.println ("The number " + n + " is : " + result);

     // Time Complexity : O(N)
     // Space Complexity : O(1)
     // This program is better than previous version as :
     // Loops runs b/w [2, bn] rather than [2, n/2]


   }
 }

Output

29 is : Prime

Method 5: Optimization by skipping even iteration

Working

In this method we’ll use the for loop to iterate through the number in the given range [3, sqrt(number)] with a step of +1. We all know that an even number can’t be a prime and the only even prime is 2. Therefore we’ll run the loop with step 1 which will skip all the even numbers.

For a given integer input we check,

  • If the number is lesser than 2.
  • If the number has any factors other than 1 and the number itself in the given range of [3, sqrt(number)].
  • We skip one iteration until the last element in reached.
  • If either of the above conditions are satisfied, then the number is not a Prime.

Java Code

Run 
public class Main
 {
   public static void main (String[]args)
   {

     int n = 29;

     if (isPrime (n))
         System.out.println (n + " is a Prime Number");
     else
         System.out.println (n + " is not a Prime Number");

   }


   static Boolean isPrime (int n)
   {
     // 0 and 1 are not prime numbers
     // negative numbers are not prime
     if (n <= 1)
       return false;

     // special case as 2 is the only even number that is prime
     else if (n == 2)
       return true;

     // Check if n is a multiple of 2 thus all these won't be prime
     else if (n % 2 == 0)
       return false;

     // If not, then just check the odds
     for (int i = 3; i <= Math.sqrt (n); i += 2)
       {
 	if (n % i == 0)
 	  return false;
       }

     return true;
   }
 }

Output

29 is : Prime

Method 6: Basic Recursion technique

Working

In this method we’ll use recursion to recursively iterate through each number and check whether it’s a factor of the number of not. To learn more about recursion in java, check out Recursion .

For a given integer input,

  • Define a recursive function with base case as follows
    • If number == iter, return True.
    • If number%iter == 0, return False.
    • If a number<2, return False.
  • Set recursive step call as checkPrime(number, iter+1).

Java Code

Run 
public class Main
{
  public static void main (String[]args)
  {

    int i = 2;
    boolean isprime= true;
    
    int n = 37;
    isprime=checkPrime(n, i);
    
    String result = isprime ? "Prime":"not Prime";
    System.out.println(n + " is : "+ result); 

  }


  static Boolean checkPrime(int n, int i)
{
    // 0, 1 and negative numbers are not prime
    if (n < 2)
        return false;

    // if this satisfies then its prime as we
    // have completed recursion from 2 to n
    if (i == n)
        return true;

    // Base cases
    if (n % i == 0)
        return false;

    i += 1;
    return checkPrime(n, i);
}
}

Output

37 is : Prime

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

11 comments on “Prime Number Program in Java”


  • Parth

    public class Main{

    public static boolean isPrime(int num){
    if(num%2==0 || num <2){
    return false;
    }
    else{
    for(int i=3;i<Math.sqrt(num);i+=2){
    if(num%i==0){
    return false;
    }
    }
    }
    return true;
    }
    public static void main(String args[]){
    int a =59;
    if(isPrime(a)) System.out.println(a + " is prime number.");
    else System.out.println(a + " is not a prime number.");
    }
    }

    0

  • imrancitb

    In the method 1, when the value of n is less than 2, the program prints “Not a Prime number” based on the condition if (n < 2). However, after that, it proceeds to the for loop where the count is checked. Since the count is below 2, it again prints "Prime number". To resolve this we can write this code:
    // Time Complexity : O(N)
    // Space Complexity : O(1)
    public class Main
    {
    public static void main (String[]args)
    {
    int n = 1;
    checkPrime(n);
    }

    private static void checkPrime(int n) {
    int count = 0;

    // checking the number of divisors b/w [1, n]
    for (int i = 1; i 2)
    System.out.println (“The given is number ” + n + ” is not prime”);
    // negative numbers, 0 and 1 are not prime
    else if (n < 2)
    System.out.println ("The given is number " + n + " is not prime");

    else
    System.out.println ("The given is number " + n + " is prime");
    }
    }

    0

    • imrancitb

      Sorry for the above code It mismatch on that code The correct code is:
      // Time Complexity : O(N)
      // Space Complexity : O(1)
      public class Main
      {
      public static void main (String[]args)
      {
      int n = 1;
      checkPrime(n);
      }

      private static void checkPrime(int n) {
      int count = 0;

      // checking the number of divisors b/w [1, n]
      for (int i = 1; i 2)
      System.out.println (“The given is number ” + n + ” is not prime”);
      // negative numbers, 0 and 1 are not prime
      else if (n < 2)
      System.out.println ("The given is number " + n + " is not prime");

      else
      System.out.println ("The given is number " + n + " is prime");
      }
      }

      0

  • Chandru

    import java.util.*;
    public class Prime {
    public static void main(String[]args)
    {
    Scanner sc=new Scanner(System.in);
    System.out.println(“Enter a number:”);
    int n = sc.nextInt();
    int count=0;
    if(n<2)
    {
    System.out.println("the number "+n+" is not a prime number");
    }
    else
    {
    for(int i = 1; i2)
    {
    System.out.println(“The number “+n+” is not a prime number”);
    }
    else
    {
    System.out.println(n+” is a prime number”);
    }
    sc.close();
    }
    }
    }

    It gets a run time input and simple logic to understand.
    Thank you.

    1

  • ankit98thakur

    Hello sir/mam, I just want to inform you that the “Method 1: Simple iterative solution” code is not appropriate for negative numbers as input.

    0

  • Sornammal

    import java.util.Scanner;
    public class Main {
    public static void main(String[] args) {
    int i;
    Scanner ip=new Scanner(System.in);
    System.out.println(“eter number : “);
    int num=ip.nextInt();
    for( i=1;i<=num;i++)
    {
    if ((6*i+1)%num==0 || (6*i-1)%num==0)
    {
    System.out.println("its prime ");
    break;
    }

    }
    for(i=2;i<num;i++)
    {
    if(num%i==0)
    {
    System.out.println("its not prime ");
    break;
    }
    }

    }
    }

    2

  • Sornammal

    import java.util.Scanner;
    public class Main{
    public static void main(String[] args)
    {
    int count=1;
    Scanner input=new Scanner(System.in);
    System.out.println(“enter number : “);
    int num=input.nextInt();
    input.close();
    for(int i=2;i2)
    {
    System.out.println(“its not prime “);
    }
    else if(count==2)
    {
    System.out.println(“its prime”);
    }
    else
    {
    System.out.println(“invalid”) ;
    }
    }
    }

    0

  • Sourav Roy

    import java.util.*;
    public class Prime_num{
    public static void main(String[] args){
    int num ;
    Scanner sc = new Scanner(System.in);
    num = sc.nextInt();
    Prime_num obj = new Prime_num();
    if(obj.isPrime(num))
    System.out.print(“The number is prime”);
    else
    System.out.print(“The number is not prime”);
    }
    boolean isPrime(int num){
    boolean var=true;
    for (int i=2;i<num/2;i++){
    if (num%i==0){
    var=false;
    break;
    }
    else
    var=true;
    }
    return var;
    }
    }

    0

  • anusha

    public class Main {

    public static void main(String[] args) {

    int num = 22;
    boolean flag = false;
    for(int i = 2; i <= num/2; ++i)
    {
    if(num % i == 0)
    {
    flag = true;
    break;
    }
    }

    if (!flag)
    System.out.println(num + " is a prime number.");
    else
    System.out.println(num + " is not a prime number.");
    }
    }

    4