javascript如何求素数

段落一：素数的定义和初级判断 素数的定义是只能被1和自身整除的正整数，这意味着其他数字都不能被它整除。判断一个数字是否是素数，我们可以从它的因数入手，即大于1且小于该数的数。JS代码如下：

  
    function isPrime(num) {
      if (num < 2) { // 质数必须大于1
        return false;
      }
      for(let i = 2; i < num; i++) { // 循环遍历除1和本身的数
        if(num % i == 0) { // 若能被整除，则不是素数
          return false;
        }
      }
      return true;
    }
  

可以看到，这个函数会返回一个布尔值，表示数字是否为素数。如果数字小于2，则必然不是质数，所以返回false。然后，函数循环遍历从2到该数字之间的所有数字，用它们试着去整除该数字，如果被整除，就说明该数字是一个合数，返回false；否则，返回true，表示该数字是质数。 段落二：优化判断方法 初步的判断方法是可以遍历每个数来判断，但对于特别大范围内的数，这种方法十分耗时，效率很低。优化的方法是通过减少遍历的数目来加快判断速度，一般会遍历未超过数字开方的数，因为一个数如果有大于开方数的因数，那么一定会有小于开方数的因数。 下面是一个优化后的素数判断函数：

  
    function isPrime(num) {
      if(num < 2) { // 质数必须大于1
        return false;
      }
      let sqrt = Math.sqrt(num);
      for(let i = 2; i <= sqrt; i++) { // 优化，只需遍历小于等于sqrt的因数
        if(num % i == 0) {
          return false;
        }
      }
      return true;
    }
  

这里代码的最大不同之处是我们使用了 Math.sqrt 函数，它可以返回给定数字的平方根。只需要遍历从2到平方根的所有数字，这样就可以减少遍历的数字数量。 段落三：查找一定范围内的素数 如果要在一定范围内找到素数，我们需要一个函数可以遍历该范围内的所有数字，调用判断函数检查它们是否是素数。下面是一个例子：

获取一定范围内的素数

  
    function getPrimes(max) {
      const primes = [];
      for(let i = 2; i <= max; i++) {
        if(isPrime(i)) {
          primes.push(i);
        }
      }
      return primes;
    }
    console.log(getPrimes(100)); //返回 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
  

在这个函数中，我们通过从2开始递增计数器，调用之前编写的 isPrime 函数来检查每个数字，并将其添加到一个数组中。最后，我们返回这个数组，其中包含小于等于给定最大数字的所有素数。 段落四：筛选法找素数 另一个有效的查找素数的算法是筛选法。该算法通过维护一个数组，初始值全是 true，表示每个位置上的数都是素数，之后会将素数的倍数设为 false，这个过程清除了大量的合数，剩下的则是素数。

  
    function sieveOfEratosthenes(max) {
      const sieve = new Array(max + 1).fill(true);
      let primes = [];

      for(let i = 2; i <= max; i++) {
        if(sieve[i]) {
          primes.push(i);
          for(let j = i * i; j <= max; j += i) {
            sieve[j] = false;
          }
        }
      }
      return primes;
    }
    console.log(sieveOfEratosthenes(100)); //返回 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
  

在这段程序中，我们通过创建一个由 true 填充的数组来存储当前数字是否为素数。则我们从 2 开始枚举并将它的倍数标记为 false。然后再找到下一个素数，重复此过程，直到达到最大数。此算法相对于之前的算法，运算速度更快。 以上是javascript求素数的方法，我们通过一些数学方法优化了求解素数的方法，不仅极大地提高了效率，同时也在性能和实用性之间作出了平衡。