Check Prime Number in Java

🔢 Prime Numbers in Java

A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. Examples include 2, 3, 5, 7, 11. Java can efficiently check primality using division and mathematical optimizations.


// Check if number is prime
boolean isPrime = true;
for (int i = 2; i <= Math.sqrt(num); i++) {
    if (num % i == 0) {
        isPrime = false;
        break;
    }
}

Different Approaches

🔍

Basic Method

Check divisibility from 2 to n-1

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

⚡

Optimized Method

Check only up to square root

for (int i = 2; i <= Math.sqrt(num); i++) {
    if (num % i == 0) {
        return false;
    }
}
return true;

🎯

Method Approach

Reusable prime checking function

public static boolean isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    
    for (int i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

🔄

While Loop

Alternative loop structure

int i = 2;
while (i <= Math.sqrt(num)) {
    if (num % i == 0) {
        return false;
    }
    i++;
}
return true;

🔹 Complete Example Program

Here's a complete Java program to check prime numbers:

import java.util.Scanner;

public class PrimeNumber {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        System.out.print("Enter a number: ");
        int number = scanner.nextInt();
        
        if (isPrime(number)) {
            System.out.println(number + " is a prime number.");
        } else {
            System.out.println(number + " is not a prime number.");
        }
        
        // Display first 10 prime numbers
        System.out.println("First 10 prime numbers:");
        int count = 0, num = 2;
        while (count < 10) {
            if (isPrime(num)) {
                System.out.print(num + " ");
                count++;
            }
            num++;
        }
        
        scanner.close();
    }
    
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }
}

Sample Output:

Enter a number: 17

17 is a prime number.

First 10 prime numbers:

2 3 5 7 11 13 17 19 23 29

🔹 Understanding Prime Logic

Prime Number Rules:

Definition: Number > 1 with exactly two factors: 1 and itself
Special cases: 1 is not prime, 2 is the only even prime
Optimization: Only check divisors up to √n
Even numbers: All even numbers > 2 are not prime

Why √n Optimization Works:

If n has a divisor > √n, it must also have one < √n
Example: For 36, √36 = 6. Divisors: 2×18, 3×12, 4×9, 6×6
We only need to check up to 6 to find all factor pairs
This reduces time complexity from O(n) to O(√n)