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 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.