Java Program to Check Whether a Number is Prime or Not

Introduction

Prime numbers are those that are divisible only by 1 and themselves. Checking whether a given number is prime is a common task in computer algorithms, particularly in fields like cryptography. Java, being a versatile programming language, provides all the tools necessary to implement this efficiently.

In this article, you will learn how to determine if a number is prime using Java. You'll explore several methods, from basic approaches suitable for smaller numbers to optimized techniques that can handle larger integers more efficiently.

Basic Prime Checking Method

Implement a Simple Prime Checker

1. Define a method named isPrime that takes an integer as a parameter.

2. Check if the number is less than 2; if so, return false because 0 and 1 are not prime.

3. Iterate from 2 up to the number less than itself, checking for divisibility.

   java Copy

   public static boolean isPrime(int num) {
       if (num <= 1) {
           return false;
       }
       for (int i = 2; i < num; i++) {
           if (num % i == 0) {
               return false;
           }
       }
       return true;
   }
   

   This function returns true if the number is prime. It checks divisibility by every integer from 2 to num - 1, and if any division has a remainder of zero, it returns false.

Using the Basic Method

1. Call the isPrime function with various numbers to check.

   java Copy

   System.out.println(isPrime(11));  // Output: true
   System.out.println(isPrime(20));  // Output: false
   

   Here, you check if 11 and 20 are prime. The function correctly identifies 11 as a prime number and 20 as non-prime.

Optimized Prime Checking Method

Reduce Search Space

1. Realize that you need to check only up to the square root of the number because a larger factor of the number would have to be multiplied by a smaller factor that has already been checked.

2. Modify the loop to run up to the square root of the number.

   java Copy

   public static boolean isPrimeOptimized(int num) {
       if (num <= 1) {
           return false;
       }
       for (int i = 2; i * i <= num; i++) {
           if (num % i == 0) {
               return false;
           }
       }
       return true;
   }
   

   In this optimized version, the loop iterates only up to the square root of num, which reduces the number of iterations, especially for large numbers.

Test the Optimized Method

1. Use the isPrimeOptimized function with larger numbers to see the efficiency.

   java Copy

   System.out.println(isPrimeOptimized(29));  // Output: true
   System.out.println(isPrimeOptimized(49));  // Output: false
   

   Here, 29 is correctly identified as prime, and 49 (7 x 7) as non-prime, showcasing quicker performance with larger numbers.

Conclusion

Determining if a number is prime in Java can be handled using various approaches depending on the size of the number and the efficiency required. Start with the simple method for understanding and basic checks, but switch to the optimized approach for handling larger numbers more efficiently. By mastering these techniques, you enhance your Java programming skills and prepare yourself for more advanced algorithms in computational mathematics.