javascriptrecursionprimesprimality-test

JavaScript: Check if number is prime with recursion


I am bit confused on how to solve this problem. I need all the prime numbers to return true. If not return false--I see that my logic is including 2 and that returns 0 so it automatically returns false, because 2 has a remainder of 0.

  

  function isPrime(num, div = 2) {
      // BASE CASE: 
     
      if(num <= div ) return false; // IF num less than OR equal to  2 RETURN false 
      
      // IF num MOD has a remainder of zero   
         
      if(num % 2 === 0) return false  // RETURN false 
      
      return true; // RETURN true
     
      // RECURSIVE CALL:

      return isPrime(num)
    }

    console.log(isPrime(1)); //-> false
    console.log(isPrime(2)); //-> true
    console.log(isPrime(3)); //-> true
    console.log(isPrime(4)); //-> false


Solution

  • There is no need for recursion. Just test all odd integers from 3 to the square root of the number as possible factors for the best performance.

    function isPrime(num){
          if(num === 2) return true;
          if(num < 2 || num % 2 === 0) return false;
          for(let i = 3; i * i <= num; i += 2)
              if(num % i === 0) return false;
          return true;
    }
    

    If you really need to use recursion, the above idea can be implemented by accepting a factor as the second argument and incrementing it by 2 when recursing.

    function isPrime(num, div = 3){
          if(num === 2) return true;
          if(num < 2 || num % 2 === 0)  return false;
          if(div * div > num) return true;
          if(num % div === 0) return false;
          return isPrime(num, div + 2);
    }