数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学使用埃拉托斯特尼筛法查找素数 JavaScript
在这个问题陈述中，我们的目标是应用埃拉托斯特尼筛法算法，借助 Javascript 功能找出素数。因此，在我们的程序中，我们将实现一个函数来查找小于给定限制的素数。
理解问题陈述
问题陈述是在 Javascript 中编写一个函数，该函数将用于查找小于给定数字的素数。为了实现此函数，我们将使用埃拉托斯特尼筛法算法。
什么是埃拉托斯特尼筛法算法？
埃拉托斯特尼筛法是一种简单且经典的算法，用于查找小于给定范围的所有素数。此算法通过定义从 2 到给定范围的所有数字的列表，然后迭代地将每个素数的倍数标记为非素数来工作。此过程将持续到所有素数都被识别为止。
此算法是查找素数的有效算法，时间复杂度为 O(n log n)。因此，可以说这种方法比检查每个数字的素性的蛮力技术快得多。
给定问题的实现
为了实现此算法，我们将创建一个大小为 n+1 的布尔数组，其中每个索引代表从 0 到 n 的数字。数组中的所有元素最初都设置为 true。这将表示每个数字都是素数。设置为 false 的前两个元素 0 和 1，因为它们不是素数。
之后，从第一个素数 2 开始，算法将遍历数组，并将所有倍数标记为合数，方法是将其在数组中的值设置为 false。现在，算法将移动到下一个未标记的数字，并重复此过程，直到找到所有素数。
最后，算法将遍历数组并收集值为 true 的所有索引。这表示它们是素数。
算法
步骤 1 − 创建一个函数 generatePrimes 来查找小于 n 个数字的素数。这里 n 是传递给函数的参数。
步骤 2 − 创建一个大小为 n+1 的数组，此数组为布尔类型，并将所有值初始化为 true。
步骤 3 − 遍历从 2 到 n 的平方根的数组。并检查当前数字是否为素数，这意味着值为 true，然后遍历其所有倍数直到 n，并将它们在数组中的值设置为 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));
复杂度
创建的函数所花费的时间为 O(n log log n)，其中 n 是布尔数组的大小。该算法从 2 迭代到 n 的平方根，并将每个素数的所有倍数标记为合数。循环迭代次数等于 n log log n，因此结果时间复杂度将为 O(n log log n)。因此，此算法对于查找素数非常有效。空间复杂度为 O(n)。
结论
埃拉托斯特尼筛法是一种查找素数的系统方法。它通过查找小于给定限制的所有非素数，并将它们标记为合数来工作。因此，剩余的数字将是素数。此算法对于小型到中型数字特别有效，并且易于在代码中实现。
1K+ 次浏览
