How to check whether given number is prime or not

Primality Test

Given an input number n, check whether any integer m from 2 to n − 1 divides n. If n is divisible by any m then n is composite, otherwise it is prime.

However, rather than testing all m up to n − 1, it is only necessary to test m up to root of n. if n is composite then it can be factored into two values, at least one of which must be less than or equal to root of n.

The efficiency can also be improved by skipping all even m except 2, since if any even number divides n then 2 does.
 It can be improved further by observing that all primes are of the form 6k ± 1, with 2 and 3 being the only exceptions. 

This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). 

So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 . This is 3 times as fast as testing all m.