正文

轻松掌握JS，轻松判断素数：掌握一招，让你的代码秒变高效！

/0 浏览量
0427

在JavaScript编程中，判断一个数是否为素数是一个常见的任务。素数，顾名思义，是指只能被1和它本身整除的大于1的自然数。例如，2、3、5、7、11等都是素数。对于编程新手来说，判断素数可能是一个小小的挑战，但对于有经验的开发者来说，这是一个展示技巧的好机会。

简单方法：试除法

最直观的方法是使用试除法。这种方法的基本思路是从2开始，一直到这个数的平方根。如果在这个范围内没有找到任何可以整除这个数的数，那么这个数就是素数。

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

这个方法简单直接，但效率不是很高，特别是对于较大的数。

优化方法：6k±1规则

有一个数学上的观察结果是，除了2和3之外的所有素数都可以表示成6k±1的形式，其中k是一个自然数。利用这个规则，我们可以进一步优化我们的判断算法。

function isPrimeOptimized(num) {
  if (num <= 1) return false;
  if (num <= 3) return true;
  if (num % 2 === 0 || num % 3 === 0) return false;

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

这个方法通过跳过所有2和3的倍数，减少了不必要的迭代，从而提高了效率。

更高效的方法：轮筛法

轮筛法是一种更高级的算法，它通过连续地筛选掉所有非素数，最终剩下的就是素数。这种方法在处理大量数时非常高效。

function sieveOfEratosthenes(limit) {
  const sieve = new Array(limit + 1).fill(true);
  sieve[0] = sieve[1] = false;

  for (let i = 2; i * i <= limit; i++) {
    if (sieve[i]) {
      for (let j = i * i; j <= limit; j += i) {
        sieve[j] = false;
      }
    }
  }

  return sieve;
}

function isPrimeUsingSieve(num) {
  const sieve = sieveOfEratosthenes(num);
  return sieve[num];
}

这个方法创建了一个布尔数组，其中每个索引代表一个数，如果这个数是素数，那么对应的索引就是true。然后，它使用轮筛法来标记非素数。

实战演练

现在，让我们来测试一下这些方法。假设我们要判断数字29是否为素数。

console.log(isPrimeSimple(29)); // 应该输出 true
console.log(isPrimeOptimized(29)); // 应该输出 true
console.log(isPrimeUsingSieve(29)); // 应该输出 true

通过以上方法，我们可以轻松地判断一个数是否为素数。选择哪种方法取决于你的具体需求，如果你只需要判断单个数，那么简单的试除法或优化后的方法就足够了。如果你需要频繁地判断多个数，那么轮筛法可能是更好的选择。

记住，编程不仅仅是写出代码，更重要的是选择合适的方法来解决问题。掌握这些技巧，让你的JavaScript代码更加高效和优雅！

-- 展开阅读全文 --