# Number Theory: Primality Test in O(sqrt(n))

A number is said to be prime if it is divisible by a number other than 1 and itself.
1 is not considered to be a prime number.

`Primality Test` is to determine whether the input integer is a prime number or not.

For instance,

5: Prime Number
12: Not a prime number
7: Prime Number
14: Not a prime number

For instance, 12 is prime because it is divisible by 2,3 and 6.

## Approach 1

``````bool isPrime(int n) {

if (n == 1) {
return false;
}

for (int i = 2; i < n; i++) {
if (n % i == 0) return false;
}

return true;
}
``````

In this method, we traverse from 1 to n, hence the time complexity, in this case, is: `O(n)`.

## Approach 2: The Better One

Now, consider a pair `a*b = n`. Here, a and b are the factors of n.
For instance,

``````n = 12
(a,b) can be (1,12),(2,6),(3,4)
``````

On observing the equation, we can infer that the maximum value of a and b can be the square root of n.

`sqrt(n)*sqrt(n) = n`

Since, if both of the values go beyond `sqrt(n)`, then `a*b` would be greater than n.

Also, If a is less than `sqrt(n)`, then b will be greater then `sqrt(n)`.
Similarly, if a is greater than `sqrt(n)`, b will be smaller than `sqrt(n)`.

We can conclude that one of the numbers is `<= sqrt(n)`, and the other one is `>= sqrt(n)`.

And to prove that n is prime, we just need to find one of the numbers - a or b.
If no such number exists, it means that n is not prime.

Hence, to do the primality test, we need not run loop till n, this can be done by running the loop till `sqrt(n)` itself.

``````bool isPrime(int n) {

if (n == 1) {
return false;
}

for (int i = 2; i*i < n; i++) {
if (n % i == 0) return false;
}

return true;
}
``````

Note: Using the libraries such as `sqrt()` can sometimes give unexpected values. Hence, instead of checking for `i < sqrt(n)` in the for loop, we check for `i*i< n`.

The loop runs from 2 to `sqrt(n)`, hence the time complexity would be `O(sqrt(n))`.

Keep Coding! :)