---
title: Prime Number Program in Java - Scaler Topics
description: In this article, by scaler topics, we're providing all the details that you need to know to build a prime number program in java.
author: Sarthak Jain
category: Java
---
:::section{.main}

Any natural number is divisible only by itself, and `1` is called a prime number. In other words, prime numbers have just two factors, i.e. `1` and number itself.

Examples: `2, 3, 5, 7, 11, 13 ......`. All natural numbers other than 1 and prime numbers are called composite numbers. In this article, we shall see how to build a prime number program in java that can help us identify whether a number is prime or not.

:::

:::section{.main}
## Prime Number Program Using a For Loop

Observe that there cannot be a divisor of a number `n` greater than `n/2`. Hence, we can divide the number `n` with only those natural numbers that are less than or equal to `n/2`. If we cannot find any factors less than or equal to its half, `n` must be a prime.

**Code:**

//check Prime Number Program in Java
public class Main {

  public static void main(String[] args) {
    // Input number
    int n = 11;

    // Holds the count of values
    int count = 0;

    // There is no prime number less than 2.
    if (n <= 1) {
      System.out.println("The number is not prime");
      return;
    }

    // Do a for loop
    for (int j = 1; j <= n / 2; j++) {
      if (n % j == 0) {
        count++;
      }
    }

    // If the number of factors is greater than 1,
    // the number is not prime.
    if (count > 1) {
        System.out.println("The number is not prime");
    }
    else {
      System.out.println("The number is prime");
    }
  }
}

**Output:-**

 The number is prime

**Explanation:** we have a variable count, initialized at zero. We start a for loop with a range 1 to half of the input number and check for divisibility at every point. If the input number is divisible by any of these, the value of the count is incremented. Once the loop ends, we check if the count is greater than 0; if yes, the number is not prime.

**Time Complexity** : `O(n)` since the loop iterates for n/2 times and ``O(n/2) = O(n)``.

**Space Complexity**: ``O(1)``, since only constant space is being used.

:::
:::section{.main}
## Prime Number Program Using a While Loop

//check Prime Number Program in Java
public class Main {

  public static void main(String[] args) {
    int n = 11;
    if (n <= 1) {
      System.out.println("The number is not prime");
      return;
    }
    int count = 0;
    int i = 1;
    while (i <= n / 2) {
      if (n % i == 0) {
        count++;
      }
      i++;
    }

    if (count > 1) {
      System.out.println("The number is not prime");
    } else {
      System.out.println("The number is prime");
    }
  }
}

**Output:**

 The number is prime

**Explanation:** Here, we have replaced the `for` loop with `while`; the rest of everything is the same as the for loop. Initially, i is 1. The value is incremented until half of the number is reached, and divisibility is checked. If the number is completely divisible at any point, it is not prime.

**Time Complexity** : ``O(n)`` since the loop iterates for n/2 times and ``O(n/2) = O(n)``

**Space Complexity**: ``O(1)``, since only constant space is being used.
:::

:::section{.main}
## Prime Number Program Using Method in Java
In this program, the same logic will be used as earlier. The only difference is, logic will be put in a different method which shall be called from the `main` method.

//check Prime Number Program in Java
class Main {

  static boolean isPrime(int n) {
    // Check if the number is <= 1
    if (n <= 1) return false;

    // Check for factors
    for (int j = 2; j <= n / 2; j++) {
      if (n % j == 0) return false;
    }
    return true;
  }

  public static void main(String[] args) {
    if (isPrime(11)) {
      System.out.println("The number is prime");
    } 
    else {
      System.out.println("The number is not prime");
    }
  }
}

**Output:-**

 The number is prime

**Explanation:** In the above code, we're checking if 11 is prime or not, which is being passed as an argument to a boolean static method `isPrime(int)`. Inside this method, we start a for loop from 2 to half the number and check for divisibility. If the input number is completely divisible by any of these, false is returned, and hence the number is not prime.

**Time Complexity** : ``O(n)`` since the loop iterates for n/2 times and ``O(n/2) = O(n)``

**Space Complexity** : ``O(1)``, since only constant space is being used.
:::
:::section{.main}
## Prime Number Program Using a Flag Variable

In this section, we shall introduce a boolean flag variable whose value will toggle based on whether a number is prime or not. As the input number becomes completely divisible, the value of the **flag variable** will toggle, and the loop will break. Let's see how to achieve this.

//check Prime Number Program in Java
class Main {

  static boolean isPrime(int n) {
    boolean flag = true;
      
    // Check if the number is <= 1
    if (n <= 1) {
      flag = false;
      return flag;
    }
      
    // Check for factors
    for (int j = 2; j <= n / 2; j++) {
      if (n % j == 0) {
        flag = false;
        break;
      }
    }
      
    return flag;
  }

  public static void main(String[] args) {
    if (isPrime(11)) {
      System.out.println("The number is prime");
    } 
    else {
      System.out.println("The number is not prime");
    }
  }
}

**Output:-**

 The number is prime

**Explanation:** The boolean variable flag is initially declared true in the method `isPrime(int)`. We enter the for loop and check for divisibility. If, at any point, the input number is completely divisible, the flag toggles to false, and the loop breaks. The value of the flag is returned.

**Time Complexity** : ``O(n)`` since the loop iterates for n/2 times in the worst case and ``O(n/2) = O(n)``

**Space Complexity** : ``O(1)``, since only constant space is being used.

:::

:::section{.main}
## Program to Display the Prime Numbers from 1 to 100
We can find all the prime numbers in a given range [here](https://www.scaler.com/topics/prime-Number-between-given-range-in-java/). Now, we have to print all the prime numbers between **1 - 100**. The logic for checking if a number is prime or not shall remain the same, i.e. **divisibility check**.

import java.lang.Math;

//check Prime Number Program in Java
class Main {

  public static void main(String[] args) {
    int i, j;
    boolean isPrime = true;

    for (i = 2; i <= 100; i++) {
      int sqrt = (int) Math.sqrt(i);
      for (j = 2; j <= sqrt; j++) {
        if (i % j == 0) {
          isPrime = false;
          break;
        }
      }
      if (isPrime) System.out.print(" " + i + " ");
      isPrime = true;
    }
  }
}

**Output:-**

 2  3  5  7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67  71  73  79  83  89  97

**Time Complexity** : O($n^2$), since for every number we're running an `O(n)` check, thus for n numbers, it will result in order of `O(n * n)` .

**Space Complexity** : ``O(1)``, since only constant space is being used.
:::

:::section{.main}
## Find Prime Numbers between Two Numbers

In this approach, we take two integers as range and then check whether the `ith` integer is prime or not.

import java.util.*;

//check Prime Number Program in Java
public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int start, end, i, j;
    boolean flag;

    System.out.print("Enter the lower bound: ");
    start = sc.nextInt();

    System.out.printf("Enter the upper bound: ");
    end = sc.nextInt();

    System.out.println("Prime numbers between " + start + " and " + end + ": ");

    for (i = Math.max(2, start); i <= end; i++) {
      if (i <= 0) continue;

      flag = true;
      int sqrt = (int) Math.sqrt(i);
        
      for (j = 2; j <= sqrt; ++j) {
        if (i % j == 0) {
          flag = false;
          break;
        }
      }
      if (flag) System.out.println(i);
    }
  }
}

**Input:-**

Enter the start number: 10
Enter the end number:20

**Output:-**

Enter the lower bound: 10
Enter the upper bound: 20
Prime numbers between 10 and 20: 
11
13
17
19

The output justifies the logic explained above.

**Time Complexity**: O($n^2$), since for every number we're running an O(n) check, thus for n numbers, it will result in order of `O(n * n)` .

**Space Complexity** : ``O(1)``, since only constant space is being used.
:::

:::section{.main}
## Find Prime Number Using Recursion

//check Prime Number Program in Java
class Main {

  static boolean isPrime(int n, int i) {
    if (n <= 2) return (n == 2) ? true : false;
    if (n % i == 0) return false;
    if (i * i > n) return true;

    return isPrime(n, i + 1);
  }

  public static void main(String[] args) {
    int n = 11;

    if (isPrime(n, 2)) {
      System.out.println("The number is prime");
    } 
    else {
      System.out.println("The number is not prime");
    }
  }
}

**Output:-**

The number is prime

**Explanation:** In the above code, we have converted the for or while loop iteration in recursion where in each call, we check for `i` and then if we do not find a result, then move to `i+1` until `i*i` is less than `n`.

:::

:::section{.summary}
## Conclusion
- Any natural number greater than 1 that is only **divisible by 1** and the number itself is called a prime number.
- The most common method to check if a number is prime is **factorization** or dividing the number by all the natural numbers smaller than it.
- The above approach can be optimized by considering only those natural numbers less than or equal to `n / 2`.
- Again, for any composite number `n`, a divisor must exist that is less than or equal to `sqrt(n)`. Thus, we can further reduce the loop space to `sqrt(n)`.
- Some of the applications of prime numbers include **error correcting** codes, calculating hash codes, computing encryption systems, etc.

:::