正文

揭秘JavaScript如何轻松计算质数个数及高效算法全解析

/0 浏览量
1024

在数字世界中，质数是一种特殊的数，它只有两个正因数：1和它本身。例如，2、3、5、7等都是质数。计算一个数字范围内质数的个数对于数学研究和计算机科学都具有重要意义。本文将深入解析如何在JavaScript中轻松计算质数的个数，并探讨高效算法的实现。

质数的定义与特性

质数是大于1的自然数，除了1和它本身外，没有其他因数。质数在数学中有着广泛的应用，如加密技术、计算机科学等领域。以下是一些关于质数的特性：

  1. 唯一分解定理：任何大于1的自然数都可以表示为质数的乘积，且这种表示是唯一的（除了因数的顺序不同）。
  2. 质数的分布：质数在自然数中的分布不是均匀的，但也没有明显的规律。

JavaScript中的质数计算

在JavaScript中，我们可以使用多种方法来计算质数的个数。下面将介绍几种常用方法，并分析它们的优缺点。

方法一：暴力法

最简单的方法是使用暴力法，即检查每个数字是否为质数。这种方法的时间复杂度为O(n√n)，其中n是待检查的数字范围。

function isPrime(num) {
  if (num <= 1) return false;
  for (let i = 2; i <= Math.sqrt(num); i++) {
    if (num % i === 0) return false;
  }
  return true;
}

function countPrimes(n) {
  let count = 0;
  for (let i = 2; i <= n; i++) {
    if (isPrime(i)) count++;
  }
  return count;
}

方法二：埃拉托斯特尼筛法（Sieve of Eratosthenes）

埃拉托斯特尼筛法是一种高效的质数筛选算法，时间复杂度为O(n log(log n))。它通过排除小于等于√n的质数的倍数来找到所有质数。

function countPrimesSieve(n) {
  if (n < 2) return 0;
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (isPrime[i]) {
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }
  return isPrime.reduce((sum, value) => sum + value, 0);
}

方法三：线性筛法

线性筛法是埃拉托斯特尼筛法的一种改进，时间复杂度与埃拉托斯特尼筛法相同，但空间复杂度更低。

function countPrimesLinearSieve(n) {
  if (n < 2) return 0;
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  const primes = [];
  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) {
      primes.push(i);
      for (let j = 0; j < primes.length && primes[j] * i <= n; j++) {
        isPrime[primes[j] * i] = false;
        if (i % primes[j] === 0) break;
      }
    }
  }
  return primes.length;
}

总结

本文介绍了JavaScript中计算质数个数的三种方法，包括暴力法、埃拉托斯特尼筛法和线性筛法。这些方法各有优缺点，选择合适的方法取决于具体的场景和需求。在实际应用中，我们可以根据计算范围和性能要求选择最合适的算法。

-- 展开阅读全文 --