In order to check prime number status...

You must have been following this to check whether a number is prime

1. Pick a number n.
2. Start with the least prime number, 2. See if 2 is a factor
of your number. If it is, your number is not prime.
3. If 2 is not a factor, check to see if the next prime, 3, is a factor. If it
is, your number is not prime.
4. Keep trying the next prime number until you reach one that is a
factor (in which case n is not prime), or you reach a prime
number that is equal to or greater than the square root of n.
5. If you have not found a number less than or equal to the square
root of n, you can be sure that your number is prime.

Very few people would know the funda behind it, well for those who don't here it is

To understand this you need to understand the concepts of factor.
Every number is made up of factors and for each factor there is factor-pair. For example lets take the number 18

18 is made of one two and two 3s.

factors of 18 can be expressed as below

1-----18
2------9
3------6

In the above representation (1,18),(2,9) and (3,6) are factor-pairs. When you multiply the factor pairs it will lead to the original number itself, in this case it's 18.

Generally for a number N, N² will have k factors less than N and k factors more than N. Now lets come to the root of your question. Let N² be a square of a number say N. Than there will be k factors less than N and k factors more than N.

For example let's take the square of a a number 6 which is 36. Now its factors are 1,2,3,4,6,9,12,18,36. Now if you notice there are 4 factors less than 6 and 4 factors more than 6 and for every factor less than 6 there is a factor pair which is more than 6.

Now if you take a prime number P there must be k factors less than square root of P and k factors more than square root of P. Since prime number will have only 1 and P as its factors there is no factor apart from 1 which is less than square root of P, this means that there can't be any factor more than square root of P as this will violate factor-pair concept. Hence you need not check for the prime numbers which is more than square root of P

Hope I am clear.



Thanks,
Quant-Master