JavaScript 使用埃拉托斯特尼筛法找到质数

在这个问题中，我们的目标是利用JavaScript的功能来应用埃拉托斯特尼筛法算法，以找出质数。因此，在我们的程序中，我们将实现一个函数来找到给定限制下的质数。

理解问题陈述

问题陈述是在Javascript中编写一个函数，该函数将用于找到给定数字以内的质数。要实现此函数，我们将使用埃拉托斯特尼筛法算法。

什么是埃拉托斯特尼筛法算法

埃拉托斯特尼筛法是一种简单而经典的算法，用于找到给定范围内的所有质数。该算法通过定义从2到给定范围的所有数字的列表，然后迭代标记每个质数的倍数为非质数来工作。这个过程将继续，直到所有质数都被确定。

这个算法是一种高效的找到质数的算法，其时间复杂度为O(n log n)。因此，我们可以说这种方法比检查每个数是否为质数的蛮力技术要快得多。

给定问题的实现

为了实现这个算法，我们将创建一个大小为n+1的布尔数组，其中每个索引将表示从0到n的数字。数组中的所有元素最初都设置为true。这将表示每个数字都是质数。前两个元素即0和1被设置为false，因为它们不是质数。

然后，从第一个质数2开始，算法将循环遍历数组，通过将数组中的值设置为false来标记所有倍数为合数。现在，算法将移动到下一个未标记的数字，并重复此过程，直到找到所有质数。

最后，算法将循环遍历数组，并收集所有具有true值的索引，这表示它们是质数。

步骤

第1步 - 创建一个generatePrimes函数，以找到n个数字的质数。这里n是传递给函数的参数。

第2步 - 创建一个大小为n+1的数组，这个数组是布尔类型的，并将其所有值初始化为true。

第3步 - 从2到n的平方根循环遍历数组。如果当前数字是质数（即值为true），则循环遍历其所有的倍数并将它们在数组中的值设置为false。

第4步 - 再次从2到n循环遍历数组，并将所有质数添加到一个结果数组中。

第5步 - 返回质数的结果数组，并在屏幕上显示用法示例。

算法的代码

function sieveOfEratosthenes(n) {
   // Create a boolean array of size n+1
   let primes = new Array(n + 1).fill(true);
   // Set first two values to false
   primes[0] = false;
   primes[1] = false;
   // Loop through the elements
   for (let i = 2; i <= Math.sqrt(n); i++) {
      if (primes[i]) {
         for (let j = i * i; j <= n; j += i) {
            primes[j] = false;
         }
      }
   }

   let result = [];
   // Loop through the array from 2 to n
   for (let i = 2; i <= n; i++) {
      if (primes[i]) {
         result.push(i);
      }
   }

   return result;
}
console.log("All prime numbers up to 20");
console.log(sieveOfEratosthenes(20));