DEV Community

Cover image for Can you check for prime numbers? - Primality Test
Farhan Yahya
Farhan Yahya

Posted on

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

Top comments (3)

Collapse
 
itsjzt profile image
Saurabh Sharma

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

Collapse
 
dochan profile image
Farhan Yahya

Great!

Collapse
 
raounek profile image
touibeg mohamed

good idea ...