How to determine if the number is prime

1. Any number greater than 3 if gives a remainder of 1 or 5 when divided by 6 then it may be a prime and if not then it’s definitely not a prime.
2. When we have to check if a number N is prime, we need to only check for its divisibility by prime factors below root(N).

 Lets check 239, 15 < root(239) < 16

Prime numbers below 15 => 2,3,5,7,11,13.

As 239 is not divisible by any of the primes below 15 hence 239 is a prime number.

• Why this works?

Whenever we have to find the factors of any number N we will get the factors in pairs (ie factor pair)
Further factor pairs will be such that in each pair,one of the factors will be lower than root(N) while other will be higher than root(N).

Extending this logic, we can say that if we are not able to find a factor upto root (N), we will not be able to find any above root (N) and hence the number will be prime.