Why do we check up to the square root of a number to determine if that number is Prime?

Why do we check up to the square root of a number to determine if that number is prime?

Prime numbers are natural numbers greater than 1 which are divisible only by 1 and itself. Examples include 2, 3, 5, 7, 11, 13, etc. (1 is neither prime nor composite).

Here is the code to check whether a number is prime or not.

As, the loop checks for each number until the sqrt(N), where N is the number to be checked, to be a factor of N. The reason for checking up to sqrt(n) only is explained as follows:-

Consider a natural number N (greater than 1) which exists as a product of two numbers a and b (assume a<=b) that is 

• N = a * b  where, 1 < a ≤ b < n

By multiplying the relation a ≤ b by a, the relation becomes:

• a² ≤ ab     

By multiplying the relation a ≤ b by b, the relation becomes: 

• ab ≤ b²

From the above-mentioned inequalities, the relation becomes: 

• a² ≤ ab ≤ b²

We know that N = a * b, so by replacing a * b with N, the following relation is obtained:

• a² ≤ N ≤ b²

Taking the square root of the equation, considering both a and b as positive numbers, we get:

• a ≤ sqrt(N) ≤ b

So, according to the above relation, it can be concluded that one of the factors of a non-prime number will definitely be less than or equal to sqrt(N).

So, while checking from 2 to the sqrt(N), if we find a number that is a factor of the N, it would mean that the number has more than 2 factors, so that number would not be a prime number. 

Otherwise, if we do not find any factor of N, that implies that the N has only 2 factors, 1 and itself, thus it is a prime number.

Examples:

Example: N = 16

√16 = 4
We can factorize 16 in pairs as : (1, 16), (2, 8), (4, 4), (8, 2), (16, 1)
In every pair, it can be observed that one factor is less than the square root.

Example: N = 36

√36 = 6
We can factorize 36 in pairs as : (1, 36), (2, 18), (3, 12), (4, 9), (6, 6), (9, 4), (12, 3), (18, 2), (36, 1)
Again, it can be observed that one factor in every pair is less than the square root of n.