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

## No comments:

## Post a Comment

Leave comments for Queries, Bugs and Hugs.