Java program to check whether a number is prime or not

Basic Concept of Prime Numbers
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, a prime number can only be divided by 1 and the number itself without leaving a remainder. 

 

For example, 2, 3, 5, 7, 11, and 13 are prime numbers. Prime numbers are fundamental in mathematics, especially in number theory, cryptography, and various algorithms.

Prime Number Checking Algorithm
To check whether a number is prime, you can use different approaches, and choosing an efficient one becomes essential as the number grows larger. Let’s explore the various ways to check if a number is prime and how to optimize the algorithm.

1. Basic Prime Number Checking
One of the simplest ways to check if a number n is prime is by dividing it by all numbers from 2 to n-1. If the number is divisible by any of these, it is not a prime number. However, this approach is inefficient, especially for large numbers. For example, if n = 1000000, you would need to check all numbers from 2 to 999999, which would take a significant amount of time.

This method has a time complexity of O(n), meaning the time it takes to run grows linearly with the size of the number.

2. Optimization Using Square Root
A more efficient way to check for prime numbers is to reduce the range of numbers we divide by. For any number n, divisors always come in pairs. For example, the divisors of 36 are:

1 x 36
2 x 18
3 x 12
4 x 9
6 x 6
As you can see, divisors come in pairs, and one of the divisors in the pair will always be less than or equal to the square root of n. Therefore, you only need to check up to the square root of n. If no number between 2 and √n divides n, then n is prime.

This approach improves the time complexity to O(√n), making it significantly faster for larger numbers.

3. Excluding Even Numbers
Another optimization is recognizing that all even numbers greater than 2 are not prime. This is because any even number can be divided by 2. So, we can skip all even numbers after checking 2. This further reduces the number of iterations and improves performance.

Detailed Breakdown of the Java Code
Now let’s break down the Java code that checks if a number is prime. I’ll explain each part in detail to show how it works and why it’s efficient.

import java.util.Scanner;

public class PrimeCheck {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // Get user input
        System.out.print("Enter a number to check if it's prime: ");
        int number = scanner.nextInt();
        
        // Call the function to check if the number is prime
        if (isPrime(number)) {
            System.out.println(number + " is a prime number.");
        } else {
            System.out.println(number + " is not a prime number.");
        }
        
        scanner.close();
    }
    
    // Function to check if a number is prime
    public static boolean isPrime(int num) {
        // 1 is not a prime number
        if (num <= 1) {
            return false;
        }
        
        // 2 is the only even prime number
        if (num == 2) {
            return true;
        }
        
        // All other even numbers are not prime
        if (num % 2 == 0) {
            return false;
        }
        
        // Check divisibility from 3 to the square root of the number
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        
        return true;
    }
}

1. Getting User Input

Scanner scanner = new Scanner(System.in);
System.out.print("Enter a number to check if it's prime: ");
int number = scanner.nextInt();

 

In this part of the code, we use the Scanner class to take input from the user. The number entered by the user is stored in the variable number, which will then be used to check whether it is a prime number.

2. Calling the Prime Check Function

if (isPrime(number)) {
    System.out.println(number + " is a prime number.");
} else {
    System.out.println(number + " is not a prime number.");
}

We call the isPrime() function with the user's input as the argument. This function will return true if the number is prime and false if it is not. Based on the result, we print whether the number is prime or not.

3. Prime Check Function

public static boolean isPrime(int num) {
    // 1 is not a prime number
    if (num <= 1) {
        return false;
    }

    // 2 is the only even prime number
    if (num == 2) {
        return true;
    }

    // All other even numbers are not prime
    if (num % 2 == 0) {
        return false;
    }

    // Check divisibility from 3 to the square root of the number
    for (int i = 3; i <= Math.sqrt(num); i += 2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

This function is where the actual logic for checking if the number is prime takes place. Let’s break it down:

Handling Numbers Less Than or Equal to 1:

if (num <= 1) {
    return false;
}

Prime numbers must be greater than 1. If the input is less than or equal to 1, the function immediately returns false.

Special Case for 2:

if (num == 2) {
    return true;
}

2 is the only even prime number, so if the input is 2, the function returns true.

Excluding Even Numbers:

if (num % 2 == 0) {
    return false;
}

Any even number greater than 2 cannot be a prime number because it is divisible by 2. If the input is an even number other than 2, the function returns false.

Divisibility Check Using the Square Root Method:

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

This part of the code checks if the input number can be divided evenly by any odd number from 3 up to the square root of the input number. If it finds a divisor, it returns false, meaning the number is not prime. If no divisors are found, the function returns true, indicating that the number is prime.

By using the square root optimization, the algorithm skips unnecessary checks and reduces the number of iterations, making it faster.

Optimizing for Performance
Apart from the optimizations already discussed, there are other ways to improve the performance of prime number checking:

Sieve of Eratosthenes: The Sieve of Eratosthenes is a classic algorithm that efficiently finds all prime numbers up to a given limit. Instead of checking each number individually, it marks the multiples of each prime starting from 2, ensuring that all composite numbers are marked. 

 

This algorithm has a time complexity of O(n log log n) and is much faster when you need to find many prime numbers.

Parallel Computing: For very large numbers or checking multiple numbers at once, parallel computing can be employed to divide the work across multiple processors, reducing the time it takes to complete the check.

Memoization: If you need to check multiple numbers for primality in the same run of a program, you can store (or "memoize") the results of previous checks to avoid recalculating for the same numbers.

Conclusion
In this explanation, we’ve covered the basics of prime numbers, efficient algorithms for checking if a number is prime, and a detailed breakdown of a Java program that implements one such algorithm.

 

Using optimizations like skipping even numbers and only checking divisibility up to the square root of the number, the program becomes much more efficient than a brute-force approach. Understanding these optimizations and applying them correctly is key to solving the problem of prime checking efficiently.