时间戳

首页 > 解决方案 > JavaScript：使用递归检查数字是否为素数

javascript - JavaScript：使用递归检查数字是否为素数

问题描述

我对如何解决这个问题有点困惑。我需要所有素数才能返回真。如果不返回 false - 我看到我的逻辑包含 2 并且返回 0 所以它自动返回 false，因为 2 的余数为 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

标签： javascriptrecursionprimesprimality-test

解决方案

不需要递归。只需测试从 3 到数字平方根的所有奇数，作为获得最佳性能的可能因素。

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;
}

如果你真的需要使用递归，可以通过接受一个因子作为第二个参数并在递归时将其递增 2 来实现上述想法。

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);
}

推荐阅读