# 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**^{2}≤ ab

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

**ab ≤ b**^{2}

From the above-mentioned inequalities, the relation becomes:

**a**^{2}≤ ab ≤ b^{2}

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

**a**^{2}≤ N ≤ b^{2}

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.