Program 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 equal to the square 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)).