Check if a Given Number is Prime

Problem Statement:

Create a Java program to check if a given number is prime.

Input:

An integer n.

Example:

Input: 29
Output: true

Step-by-Step Solution:

Step 1: Handle Special Cases

• A number less than or equal to 1 is not prime. Numbers 2 and 3 are prime.

if (n <= 1) return false;
if (n <= 3) return true;

Step 2: Check Divisibility

• If the number is divisible by 2 or 3, it is not prime.

if (n % 2 == 0 || n % 3 == 0) return false;

Step 3: Use 6k ± 1 Optimization

• For numbers greater than 3, check for factors up to the square root of n using the 6k ± 1 optimization. This helps in reducing the number of checks.

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

Complete Solution:

public class PrimeCheck {
    public static void main(String[] args) {
        int number = 29;
        System.out.println("Is " + number + " prime? " + isPrime(number));
    }

    public static boolean isPrime(int n) {
        // Step 1: Handle special cases
        if (n <= 1) return false;
        if (n <= 3) return true;

        // Step 2: Check for divisibility by 2 and 3
        if (n % 2 == 0 || n % 3 == 0) return false;

        // Step 3: Check for factors up to square root of n
        for (int i = 5; i * i <= n; i += 6) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
        }

        return true;
    }
}

Explanation:

• Special Cases: Directly handle small numbers for simplicity.
• Divisibility Check: Quickly rule out even numbers and multiples of 3.
• 6k ± 1 Optimization: Efficiently check for factors by reducing the number of iterations required.

Example:

int num = 31;
boolean result = isPrime(num);
System.out.println(num + " is prime? " + result); // Output: true