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! :)

## Top comments (3)

i*i<=n.........

kindy correct.........

your code not working for 9.

it should be i*i<=n

(I know it's late, but....I had to)

There is this article that optimized it furthermore....

geeksforgeeks.org/primality-test-s...

Because I checked it over some coding platform with the correction of @starlord and it still fails to pass some test cases.