Prime Numbers in Java

Last updated: February 8, 2025

Prime numbers are an important topic in mathematics and computer science. Many programming problems, including competitive coding challenges, require a strong understanding of prime number logic. In this guide, we will explore what prime numbers are and how to determine whether a number is prime using Java, with several optimized approaches.

What is a Prime Number?

A prime number is a natural number greater than 1 that has exactly two divisors:

• 1
• Itself

Examples of prime numbers include:

2, 3, 5, 7, 11, 13, 17, 19, 23, ...
  

Numbers like 4, 6, 8, 9, 10… are not prime because they have more than two divisors.

Java Program: Check Prime Using Loop

This is the simplest and most beginner-friendly method.

import java.util.Scanner;

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

        System.out.print("Enter a number: ");
        int n = sc.nextInt();

        boolean isPrime = true;

        if (n <= 1) {
            isPrime = false;
        } else {
            for (int i = 2; i <= n / 2; i++) {
                if (n % i == 0) {
                    isPrime = false;
                    break;
                }
            }
        }

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

Optimized Prime Check (Iterate till √n)

Instead of checking all numbers up to n/2, we can check only up to √n. This makes the code much faster, especially for large values.

public class PrimeOptimized {

    public static boolean isPrime(int n) {
        if (n <= 1) return false;

        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

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

        if (isPrime(n))
            System.out.println(n + " is Prime.");
        else
            System.out.println(n + " is Not Prime.");
    }
}
  

Prime Numbers in a Range

This program prints all prime numbers in a given range:

public class PrimeRange {

    public static boolean isPrime(int n) {
        if (n <= 1) return false;

        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println("Prime numbers between 1 and 100:");

        for (int i = 1; i <= 100; i++) {
            if (isPrime(i))
                System.out.print(i + " ");
        }
    }
}
  

Prime Number Using Recursion

This is more of a conceptual method. Recursion is not the most efficient way, but useful for understanding logic.

public class PrimeRecursion {

    public static boolean checkPrime(int n, int i) {
        if (i * i > n)
            return true;
        if (n % i == 0)
            return false;

        return checkPrime(n, i + 1);
    }

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

        if (n > 1 && checkPrime(n, 2))
            System.out.println(n + " is Prime.");
        else
            System.out.println(n + " is Not Prime.");
    }
}
  

Conclusion

Prime number checking is one of the fundamental concepts of programming. For beginners, the loop method is easy to understand. For real-world applications, the √n optimized method is highly recommended, especially when dealing with large inputs or ranges.