Prime number test

 We know that the prime numbers are the natural numbers greater than 1 and divisible by only 1 and the number itself. Any natural number greater than 1 which is divisible by more than two factors, that is a composite number. Today, we will know the way to test whether the given number is prime or not.

Trial division 

Trial division is the primality test. The idea is that:

If a number n is to be checked whether it is a prime or not, we simply need to see if it is divisible by any prime number between 2 and √n, it is composite otherwise it is prime.

For example, if  we take n=61.

We need to check the prime numbers between 2 and √61. It means upto 7 because 7<√61<8. 

These prime numbers are 3, 5, 7 and none of these divides 61. So 61 is prime.

Why to check upto √n and not above?

The simple answer to this question is that for any number greater than or equal to √n to be the divisor of n, there must be a divisor of n less than √n. We explain it by example:

Let's consider n=60.

The factors are as follows.

2×30, 3×20, 4×15, 5×12, 6×10, 10×6, 12×5, 15×4, 20×3, 30×2

Note, after 6×10, all the factors are repeating just in a reverse order. So that's why there is no need to check after √n.