Primality Test - Naive Methods

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 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(n) 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.

Labels: , ,