质数是恰好有两个完美约数的数字。我们将看到两种查找给定范围内素数数量的方法。第一种是使用暴力法，这种方法时间复杂度有点高。然后我们将改进这个方法，并采用埃拉托色尼筛法算法以具有更好的时间复杂度。在本文中，我们将使用 JavaScript 编程语言查找给定范围内的素数总数。
暴力法
首先，在这个方法中，我们将学习如何找到一个数字是否是素数，我们可以通过两种方法找到它。一种方法的时间复杂度为 O(N)，另一种方法的时间复杂度为 O(sqrt(N))。
判断一个数是否为素数的直接法
示例
首先，我们会进行for循环，直到得到一个数，并统计能整除该数的数，如果能整除该数的数不等于2，则该数不是质数，否则number 是质数。让我们看看代码 –
function isPrime(number){ var count = 0; for(var i = 1;i<=number;i++) { if(number%i == 0){ count = count + 1; } } if(count == 2){ return true; } else{ return false; }}// checking if 13 and 14 are prime numbers or not if(isPrime(13)){ console.log("13 is the Prime number");}else{ console.log("13 is not a Prime number")}if(isPrime(14)){ console.log("14 is the Prime number");}else{ console.log("14 is not a Prime number")}
在上面的代码中，我们从 1 到 number 进行遍历，在 number 范围内找到能整除给定数字的数字，并得到有多少个数字能整除给定数字，并打印结果以此为基础。
立即学习“Java免费学习笔记（深入）”；
上述代码的时间复杂度为 O(N)，检查每个数字是否为素数将花费 O(N*N)，这意味着这不是一个好的检查方法。
数学方法
我们知道，当一个数完全整除另一个数时，商也是一个完全整数，也就是说，如果一个数 p 可以被一个数 q 整除，则商为 r，即 q * r = p。 r 也可以将数 p 与商 q 整除。因此，这意味着完美除数总是成对出现。
示例
通过上面的讨论，我们可以得出结论，如果我们只检查除法到 N 的平方根，那么它将在非常短的时间内给出相同的结果。让我们看看上面方法的代码 –
function isPrime(number){ if(number == 1) return false var count = 0; for(var i = 1;i*i<=number;i++){ if(number%i == 0){ count = count + 2; } } if(count == 2){ return true; } else{ return false; }}// checking if 67 and 99 are prime numbers or not if(isPrime(67)){ console.log("67 is the Prime number");}else{ console.log("67 is not a Prime number")}if(isPrime(99)){ console.log("99 is the Prime number");}else{ console.log("99 is not a Prime number")}
在上面的代码中，我们刚刚通过更改 for 循环的范围来更改之前的代码，因为现在它只会检查 N 个元素的第一个平方根，并且我们将计数增加了 2。
算家云
高效、便捷的人工智能算力服务平台
37 查看详情
上述代码的时间复杂度为O(sqrt(N))，较好，这意味着我们可以使用该方法来查找给定范围内存在的素数的个数。
L 到 R 范围内的素数个数
示例
我们将在范围内实现之前给出的代码，并计算给定范围内的素数数量。让我们实现代码 –
function isPrime(number){ if(number == 1) return false var count = 0; for(var i = 1;i*i<=number;i++) { if(number%i == 0){ count = count + 2; } } if(count == 2){ return true; } else{ return false; }}var L = 10var R = 5000var count = 0for(var i = L; i <= R; i++){ if(isPrime(i)){ count = count + 1; }}console.log(" The number of Prime Numbers in the given Range is: " + count);
在上面的代码中，我们使用 for 循环遍历了从 L 到 R 的范围，并且在每次迭代时，我们都检查当前数字是否是质数。如果该数字是素数，那么我们就增加计数，最后打印该值。
上述代码的时间复杂度为 O(N*N)，其中 N 是 Range 中的元素数量。
埃拉托色尼算法筛选
示例
埃拉托斯特尼筛法算法工作效率很高，可以在 O(Nlog(log(N))) 时间内找到给定范围内的素数个数，与其他算法相比，速度非常快。筛子占用的空间是 O(N)，但这并不重要，因为时间非常有效。让我们看看代码，然后我们将转向代码的解释 –
var L = 10var R = 5000var arr = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,1);arr[0] = 0arr[1] = 0for(var i = 2;i<=R;i++){ if(arr[i] == 0){ continue; } for(var j = 2; i*j <= R; j++){ arr[i*j] = 0; }}var pre = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,0);for(var i = 1; i<= R;i++){ pre[i] = pre[i-1] + arr[i];}answer = pre[R]-pre[L-1]console.log("The number of Prime Numbers in the given Range is: " + answer);
在上面的代码中，我们看到了埃拉托斯特尼筛的实现。首先，我们创建了一个包含大小为 R 的数组，之后我们使用 for 循环遍历了该数组，并且对于每次迭代，如果当前数字不是 1，则意味着它不是素数，否则它是素数，并且我们已经删除了所有小于 R 且当前质数的倍数的数。然后我们创建了一个前缀数组，它将存储从 0 到当前索引的素数计数，并且可以在恒定时间内提供 0 到 R 范围内每个查询的答案。
时间和空间复杂度
上述代码的时间复杂度为 O(N*log(log(N)))，与 O(N*N) 和 O(N*(sqrt(N)) 相比要好得多）。与之前的代码相比，上述代码的空间复杂度更高，为 O(N)。
结论
在本教程中，我们了解了如何使用 JavaScript 编程语言查找给定范围内的素数个数。质数是恰好有两个完美约数的数字。 1 不是质数，因为它只有一个完美约数。我们已经看到了时间复杂度为 O(N*N)、O(N*sqrt(N)) 和 O(N*log(log(N))) 的三种方法。另外，前两种方法的空间复杂度为 O(1)，埃拉托色尼筛法的空间复杂度为 O(N)。
以上就是用于计算范围内素数的 JavaScript 程序的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/530277.html
微信扫一扫 
支付宝扫一扫 
