This is one of the simple programs most developers really don't know how to go about. Just imagine getting such this question wrong at a coding interview while you aced all the language specific questions. That will be so sad.

In this post we'll look at how to check whether a value is prime or not using a primality test known as **TRIAL DIVISION**.

## LITTLE EXPLANATION

Now, let's look at how one might go about this problem. Since a prime number is a number with just two divisors (1 and the number itself), a way to solve this problem is to try dividing the number by values between 1 and itself. If none divides perfectly then it's a prime number else it isn't. Hence, the code below

```
function isPrime(n){
for(let i = 2; i < n; i++){
if(n % i == 0) return false;
}
return true;
}
```

But guess what? the downside of this code is when it actually finds a prime number. Because to find a prime number the for loop has to run n-2 times. So let's say you are to check whether **13441** is a prime number, then that mean we need **13439** iterations which is too much and what if we are to check for 10^{6} numbers? that's lot's of time and computing power. **Hence, we have a nice way of cutting off some of the work.**

## TRIAL DIVISION

With this method, we use a simple mathematical analysis to cut off most of the work that is to be done.

The idea is that: For any composite number(a composite number is the opposite of a prime number) the first divisor apart from 1 can be found between 1 and root of n (where n is the number to be tested).

eg. checking whether 100 is prime.

numbers between 1 and root(100) are 2,3,4,5,6,7,8,9

and fortunately 2 is a divisor of 100.

This method reduces the number of iterations exponentially making our code look like below

```
function isPrime(n){
for(let i = 2; i*i <= n; i++){ // difference on this line i*i
if(n % i == 0) return false;
}
return true;
}
```

So the logic is to iterate from 2 to root(n).

hence the condition **i<=root(n)**,

squaring both sides will give the condition **i*i<=n**

And with this, to check whether **13441** is prime we only iterate **115** times instead of **13439** times.

Hope you learnt something today. Thanks

## Top comments (3)

This is a nice approach to reduce computing I have used this in solving euler problems

Great!

good idea ...