# Problem

Given a number N, determine if it is a prime.

# What is a Prime Number?

A prime number is a positive number greater than 1 which has no positive divisor except for 1 and itself. For example, 2, 3, 5, 11 are prime numbers. Whereas 4, 6 are non-prime or composite numbers.

# O(N) Solution

From the definition, we can easily construct a Primality Test function that can determine if a given number N is prime or not. Let us call it isPrime() function.

bool isPrime ( int n ) {
if ( n <= 1 ) return false; // n needs to be greater than 1
for ( int i = 2; i < n; i++ ) {
// If it is possible to divide n with a number other than 1 and n, then it is not prime
if ( n % i == 0 ) return false;
}
return true; // Otherwise, this is prime
}


The code simply iterates over all values between 2 and N-1 and checks if it can divide N. It has a complexity of O(N).

We can observe that, when $i$ is greater than $n/2$, it will never divide $n$. Hence, we can optimize it a bit.

bool isPrime ( int n ) {
if ( n <= 1 ) return false;
for ( int i = 2; i <= n / 2; i++ ) {
if ( n % i == 0 ) return false;
}
return true;
}


This, however, does not change the complexity.

# O($\sqrt{N}$) Solution

We can further optimize the Primality Test from the following observation. Let us consider A and B such that $N=A \times B$. Now notice that, when $A = \sqrt{N}$, B is also $\sqrt{N}$. Otherwise, $A \times B$ would not be equal to $N$. What happens when $A > \sqrt{N}$? In order for $A \times B$ to be equal to $N$, $B$ must be $< \sqrt{N}$.

So using the following observation, we can claim that if $N$ has a divisor which is $>= \sqrt{N}$, then it also has a divisor which is $< = \sqrt{N}$.

For example, $12$.

$12 = 1 \times 12$
$12 = 2 \times 6$
$12 = 3 \times 4$
$12 = \sqrt{12} \times sqrt{12}$

Every divisor $>= \sqrt{N}$ has a complementary divisor which is $<= \sqrt{N}$.

This means that if we fail to find any divisor of $N$ below $\sqrt{N}$ then it is safe to assume we will not find any divisor above $\sqrt{N}$.

bool isPrime ( int n ) {
if ( n <= 1 ) return false;
int sqrtn = sqrt(n);
for ( int i = 2; i <= sqrtn; i++ ) {
if ( n % i == 0 ) return false;
}
return true;
}


Notice that I defined a new variable sqrtn instead of simply writing i <= sqrt(n) in line 4. That's because the function sqrt() has a complexity of O(√N) and writing it inside for loop condition would mean that the function would get called unnecessarily every time the loop iterates.