Can you check for prime numbers? - Primality Test

This is one of the simple programs most developers really don't know how to go about. Just imagine getting such this question wrong at a coding interview while you aced all the language specific questions. That will be so sad.

In this post we'll look at how to check whether a value is prime or not using a primality test known as TRIAL DIVISION.

LITTLE EXPLANATION

Now, let's look at how one might go about this problem. Since a prime number is a number with just two divisors (1 and the number itself), a way to solve this problem is to try dividing the number by values between 1 and itself. If none divides perfectly then it's a prime number else it isn't. Hence, the code below

function isPrime(n){
  for(let i = 2; i < n; i++){
    if(n % i == 0) return false;
  }
  return true;
}

But guess what? the downside of this code is when it actually finds a prime number. Because to find a prime number the for loop has to run n-2 times. So let's say you are to check whether 13441 is a prime number, then that mean we need 13439 iterations which is too much and what if we are to check for 10⁶ numbers? that's lot's of time and computing power. Hence, we have a nice way of cutting off some of the work.

TRIAL DIVISION

With this method, we use a simple mathematical analysis to cut off most of the work that is to be done.

The idea is that: For any composite number(a composite number is the opposite of a prime number) the first divisor apart from 1 can be found between 1 and root of n (where n is the number to be tested).
eg. checking whether 100 is prime.
numbers between 1 and root(100) are 2,3,4,5,6,7,8,9
and fortunately 2 is a divisor of 100.
This method reduces the number of iterations exponentially making our code look like below

function isPrime(n){
  for(let i = 2; i*i <= n; i++){ // difference on this line i*i
    if(n % i == 0) return false;
  }
  return true;
}

So the logic is to iterate from 2 to root(n).
hence the condition i<=root(n),
squaring both sides will give the condition i*i<=n

And with this, to check whether 13441 is prime we only iterate 115 times instead of 13439 times.

Hope you learnt something today. Thanks

Comments

[Saurabh Sharma]

This is a nice approach to reduce computing I have used this in solving euler problems

[Farhan Yahya]

Great!

[touibeg mohamed]

good idea ...