### 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.