Finding Prime Number using Java

Prime numbers are integers that are only divisible by 1 and themselves. In other words, a prime number cannot be divided evenly by any other number except 1 and itself. In this tutorial, we will write a Java program to determine if a given number is prime or not.

Step 1: Understanding the logic

To determine if a number is a prime, we can use a simple algorithm that checks if the number is divisible by any number between 2 and the square root of the number. If the number is divisible by any of these numbers, then it is not prime. Otherwise, it is prime.

Step 2: Writing the Java code

Let’s start by writing a Java function that checks if a given number is prime or not.

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

This function takes an integer as input and returns true if the number is prime and false if it is not.

Here’s how the function works:

  • First, we check if the number is less than or equal to 1. If it is, then it is not prime, so we return false.
  • Next, we loop through all numbers between 2 and the square root of the number. For each number, we check if the number is divisible by that number. If it is, then it is not prime, so we return false.
  • If we have looped through all numbers and none of them divide the number evenly, then the number is prime, so we return true.

Step 3: Testing the code

Now that we have written the isPrime function, let’s test it with some sample inputs.

public static void main(String[] args) {
    int num1 = 7;
    int num2 = 12;
    if (isPrime(num1)) {
        System.out.println(num1 + " is a prime number");
    } else {
        System.out.println(num1 + " is not a prime number");
    }
    if (isPrime(num2)) {
        System.out.println(num2 + " is a prime number");
    } else {
        System.out.println(num2 + " is not a prime number");
    }
}

This code tests the isPrime function with two numbers, 7 and 12. The output of this program should be:

7 is a prime number
12 is not a prime number

Step 4: Optimizing the code

The isPrime function works correctly, but it can be optimized further. One optimization we can make is to check if the number is even before looping through all odd numbers between 3 and the square root of the number. If the number is even and not 2, then it is not prime.

Here is the optimized version of the isPrime function:

public static boolean isPrime(int n) {
    if (n <= 1) {
        return false;
    }
    if (n == 2 || n == 3) {
        return true;
    }
    if (n % 2 == 0 || n % 3 == 0) {
        return false;
    }
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

Here is how this optimized version works:

  • if (n <= 1) { return false; }: This line checks if the input number n is less than or equal to 1. If n is less than or equal to 1, the function returns false because 1 and all numbers less than 1 are not considered prime.
  • if (n == 2 || n == 3) { return true; }: This line checks if the input number n is equal to 2 or 3. If n is equal to 2 or 3, the function returns true because 2 and 3 are the only two prime numbers that are less than or equal to 3.
  • if (n % 2 == 0 || n % 3 == 0) { return false; }: This line checks if the input number n is divisible by 2 or 3. If n is divisible by 2 or 3, the function returns false because all even numbers (except 2) and all numbers divisible by 3 are not considered prime.
  • for (int i = 5; i * i <= n; i += 6) {: This line starts a for loop that checks only prime numbers in the form of 6k+1 and 6k-1 less than or equal to the square root of n. The loop increments i by 6 in each iteration because all other numbers that are not in the form of 6k+1 or 6k-1 can be represented as the product of these prime numbers.
  • if (n % i == 0 || n % (i + 2) == 0) { return false; }: This line checks if n is divisible by either i or i+2. If n is divisible by either of these two prime numbers, the function returns false because n is not a prime number.
  • return true;: If none of the previous conditions have returned false, the function returns true because n is a prime number.

Also, see the example code JavaExamples_NoteArena in our GitHub repository. See complete examples in our GitHub repositories.

Follow us on social media
Follow Author