Introduction:

Prime Number is an integer greater than 1 and only divisible by 1 and itself. For instance – 2, 3, 5, 7, 11, 13 etc are all prime numbers.

In other words, any number with only two factors – 1 and the number itself is known as a prime number.

Numbers like 4, 8, 12 are not prime or rather composite numbers.

Brute-Force Approach:

A brute-force algorithm to check whether a number is prime or not would be:

boolean isPrimeNumber(int number) {
    if(number < 2)
        return false;
    for(int div = 2; div < number; div++) {
        if(number % div == 0)
            return false;
    }
    return true;
}

Here, we are iterating from 2 to number-1 and checking if the div is a factor of ‘number’ at each iteration.

Clearly, if we find any factor of the ‘number’ in the range: 2 to (number -1), it is a non-prime or composite number.

Time Complexity: O(n)

Enhanced Solution:

As programmers, we keep on asking – ‘Can we do better?’

The answer here is ‘Yes!’. We can use the mathematical fact –

“If a number has no factors starting from 2 to sqrt(number), then that number will always be a prime number.”

to optimize our solution.

The idea behind it is that say if 2 divides a number N, then N/2 also divides N. Similarly, if 3 divides N, then N/3 would also be a valid factor of N and so on. If we go on with this, we’ll realize the middle point is sqrt(n).

So clearly, we only need to check only up to the sqrt of that number. Let’s look at the implementation:

boolean isPrimeNumber(int number) {
    if(number < 2)
        return false;
    for(int div = 2; div <= Math.sqrt(number); div++) {
        if(number % div == 0)
            return false;
    }
    return true;
}

We can also rephrase the above code as:

boolean isPrimeNumber(int number) {
    if(number < 2)
        return false;
    for(int div = 2; div * div <= number; div++) {
        if(number % div == 0)
            return false;
    }
    return true;
}

Time Complexity: O(sqrt(n))

Further Optimization:

There is a further scope of optimization to the above solution. If we clearly notice the pattern of prime numbers, we’ll realize 2 is the only even-prime number. We can use this fact to our advantage and further optimize our code:

boolean isPrimeNumber(int number) {
    if(number == 2)  return true;
    if(number < 2 || number % 2 == 0) return false;
    //only odd-number checks
    for(int div = 3; div*div <= number; div+=2){
        if(number % div == 0)
            return false;
    }
    return true;
}

Conclusion:

In this tutorial, we looked at ways in which we can check if a given number is prime or not.

Also, we can choose to use Java 8 IntStream to reduce our lines of code.