# Prime Number Test Algorithm

Week 7 at Hack Reactor, I came across a common interview algorithm question:

Write a function that takes in a input of integer greater or equal to 0, it will output true or false base on whether the number is a Prime Number

A prime number is an integer greater than 1 that has no divisors other than itself and 1.

It is a fairly simple question without considering efficiency (number of operations). However, if we take efficiency in consideration, we will need to apply some tricks.

First, I will show the most basic version solution. Please see below:

function primeTester (n) {

//take out edge case 0 and 1

if(n<=1) return false;

//go from 3 since 2 is a prime number

for(var i=3; i<n; i++){

//check if n is divisible by i

if(n%i ===0 ) return false

}

//if passed all out test

return true;

}

This solution simply iterate from 3 to the input number, and check if the number is divisible by any of the iteration. If it is, we can immediately return false. The if statement is just to handle the edge case of 1 and 0, in which are Not prime numbers. This solution works, however, it is not optimize in which it does many unnecessary iterations.

To optimize the solution, we must cut down on the number of iteration. We need to think more mathematically. If a number is divisible by 2 or 3, we can eliminate them right away. So please see the solution below:

function primeTester (n) {

//take out edge case 0 and 1

if(n<=1) return false;

//return false if divisible by 3

if(n%3===0 && n>3) return false;

//return false if divisible by 2

if(n%2===0 && n>2) return false;

//start from 5 and only go up to square root of n

for(var i=5; i<=Math.sqrt(n);i+=6){

//check in interval of 6 from 5

if(n%i ===0 ) return false

//check in interval of 6 from 7

if(n%(i+2) === 0) return false;

}

//if passed all out test

return true;

}

In this solution, we cut down the number of operations dramatically if the input number is large. First, we eliminate number that is divisible by 2 or 3 right away. Then we cut down the for loop iteration by square rooting the input number. This is valid because the smallest divisible of any number will never be greater than the square root of number itself. For example:

Number: 9

square root of 9 is 3

smallest divisible number is 3

Number: 456.708

square root of 45 is

smallest divisible number is 3

Whenever you have a large number, this second solution will make a huge difference! Thanks again for reading and happy coding everyone =D!