We will be implementing a program to check if the given number is prime or not in Javascript and return true
or false
.
Prime Number: A number that is divisible by only 1 and itself.
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 ofn
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 ofn
, so Space complexity is O(sqrt(n)).