How to check whether a number is Prime or not?

Let N be a number.

Do the following steps to check if N is a prime or not.

1. Find the square root of N. 

      Let the square root of N be m. 

           √N=m

2. If m is a natural number

   then N is a composite number since the root of N is a whole number and it's obvious that m is a factor of N.

else

3. If m is not a natural number (i,e. if m is a fraction)

→increase it to the next natural number.

    let it be m'.

→Then divide the given number (N) by all the prime numbers below m'.

→If N is divisible by any of these prime numbers then it is a composite number else it is a prime number.

Example 1:

Check if 289 is prime or not.

Find the square root of 289

√289=17

Since the root (17) is a natural number, it's also a divisor of 289.

Hence 289 is not a prime number.

Example 2:

Check whether 347 is prime or not.

Find the square root of 347

√347=18.627

The square root of 347 is a fractional number

So increase the root to the next natural number.

18.627≃19

Now divide 347 by all primes below 19.

The primes below 19 are 2,3,5,7,11,13,17

347/2 (Remainder 1)

347/3(Remainder 2)

347/5(Remainder 2)

347/7(Remainder 4)

347/11(Remainder 6)

347/13(Remainder 9)

347/17(Remainder 7)

So none of the primes below 19 divides 347.

Hence 347 is a Prime Number.