Is a number prime

A prime number is divisible by {1, itself}

import java.util.Scanner;

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

        // Input: Reading n takes O(1) time
        int n = new Scanner(System.in).nextInt();

        method1(n); // Calls method1
        method2(n); // Calls method2
        method3(n); // Calls method3
    }

    // Method 1: Brute Force Approach
    // Time Complexity (TC): O(n) in the worst case
    // - Best case (n=2): O(1), no iteration
    // - Average case: O(n)
    // - Worst case (n is prime): O(n)
    // Space Complexity (SC): O(1)
    private static void method1(int n) {

        boolean isPrime = true; // O(1) space - a single boolean variable

        // Loop runs (n - 2) times in the worst case
        // Time Complexity: O(n)
        for (int i = 2; i < n; i++) {
            if (n % i == 0) {  // Checking modulo takes O(1)
                isPrime = false; // O(1) - simple boolean assignment
                break; // Breaks out early if a divisor is found
            }
        }

        // Output is a constant-time operation: O(1)
        System.out.println(n + (isPrime ? " is prime" : " not prime"));
    }

    // Method 2: Half-Range Optimization
    // Time Complexity (TC): O(n/2) = O(n) in the worst case
    // - Best case (n=2): O(1), no iteration
    // - Average case: O(n/2)
    // - Worst case (n is prime): O(n/2)
    // Space Complexity (SC): O(1)
    private static void method2(int n) {

        boolean isPrime = true; // O(1)

        // Loop runs (n/2 - 2) times in the worst case
        // Time Complexity: O(n/2)
        for (int i = 2; i <= n / 2; i++) {
            if (n % i == 0) {  // Checking modulo takes O(1)
                isPrime = false; // O(1)
                break; // Breaks out early if a divisor is found
            }
        }

        // Printing result takes O(1)
        System.out.println(n + (isPrime ? " is prime" : " not prime"));
    }

    // Method 3: Square-Root Optimization
    // Time Complexity (TC): O(sqrt(n)) in the worst case
    // - Best case (n=2): O(1), no iteration
    // - Average case: O(sqrt(n))
    // - Worst case (n is prime): O(sqrt(n))
    // Space Complexity (SC): O(1)
    private static void method3(int n) {

        boolean isPrime = true; // O(1)

        // Loop runs sqrt(n) times in the worst case
        // Time Complexity: O(sqrt(n))
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {  // Checking modulo takes O(1)
                isPrime = false; // O(1)
                break; // Breaks out early if a divisor is found
            }
        }

        // Printing result takes O(1)
        System.out.println(n + (isPrime ? " is prime" : " not prime"));
    }

🔍 Why use i * i <= n instead of i <= sqrt(n)?
Because:
Math.sqrt(n) is a costly function (and uses floating-point math)
i * i <= n is simple and uses only integers — faster and more efficient

}