Program to check the prime number

An algorithm to check the prime number.

We will be implementing a program to check if the given number is prime or not in javascript and return true or false.

Example

Input:
1
2
3
4
31
37

Output:
false
true
true
false
true
false

We are going to use two different approaches to check if given number is prime or not.

• A brute force solution.
• A recursive solution.

A brute force solution

Implementation

• We are going to check if the given number is less than 2 or not, If it is less then it is not prime and return false.
• If the number is not less than 2 and it is divisible by any number less than the sqaure root of the given number then also it is not prime and return false.
• Else it is prime and return true.
• Everything is written in ES6.

let isPrime = (n) => {
  //if n is less than 2 return false
  if(n < 2){
    return false;
  }
  
  //check if n is divisible number less than its sqaure root
  for(let i = 2; i  <= Math.sqrt(n); i++) {

     //if it divisible then return false
     if(n % i == 0){
        return false;
     }
  }

  //Else return true
  return true;
}

Time complexity: O(sqrt(n)).
Space complexity: O(1).

Time and Space complexity

• We are looping until i is less than or eqaul to the sqare root of the given number, so Time complexity is O(sqrt(n)).
• We are using constant space, so Space complexity is O(1).

Recursive solution

Implementation

• We will implement the same brute force method in recursive solution.

let primeNumberRecursive = (n, i = 2) => {
   //Check if number is less than or equal 2  
   if(n <= 2){
       //if number is equal to 2 then return true
       return (n == 2 )? true : false;
    }
    
    //if number is divisible by any number then return false
    if( n % i == 0){
       return false;
    }
    
    //if number is greater than square root of the given number this return true
    // it is same as i > Math.sqrt(n)
    if( i * i > n ){
       return true;
     }
   
   //call the same function with incremented value of i  
   return primeNumberRecursive(n, i+1);
 }

Time complexity: O(sqrt(n)).
Space complexity: O(sqrt(n)).

Time and Space complexity

• We are recursively calling the function until i is less than square root of given number. so it will call the function less than square root of n times, so Time complexity is O(sqrt(n)).
• We will be call the function recursively and all the function will stored in call stack, we will be calling the function until i is less than square root of n, so Space complexity is O(sqrt(n)).