质数是恰好有两个完美约数的数字。我们将看到两种查找给定范围内素数数量的方法。第一种是使用暴力法，这种方法时间复杂度有点高。然后我们将改进这个方法，并采用埃拉托色尼筛法算法以具有更好的时间复杂度。在本文中，我们将使用 JavaScript 编程语言查找给定范围内的素数总数。

暴力法

首先，在这个方法中，我们将学习如何找到一个数字是否是素数，我们可以通过两种方法找到它。一种方法的时间复杂度为 O(N)，另一种方法的时间复杂度为 O(sqrt(N))。

判断一个数是否为素数的直接法

示例

首先，我们会进行for循环，直到得到一个数，并统计能整除该数的数，如果能整除该数的数不等于2，则该数不是质数，否则number 是质数。让我们看看代码 -

function isPrime(number){
   var count = 0;
   for(var i = 1;i
<p>在上面的代码中，我们从 1 到 number 进行遍历，在 number 范围内找到能整除给定数字的数字，并得到有多少个数字能整除给定数字，并打印结果以此为基础。</p>
<p>上述代码的时间复杂度为 O(N)，检查每个数字是否为素数将花费 O(N*N)，这意味着这不是一个好的检查方法。</p>
<h2>数学方法</h2>
<p>我们知道，当一个数完全整除另一个数时，商也是一个完全整数，也就是说，如果一个数 p 可以被一个数 q 整除，则商为 r，即 q * r = p。 r 也可以将数 p 与商 q 整除。因此，这意味着完美除数总是成对出现。</p>
<h3>示例</h3>
<p>通过上面的讨论，我们可以得出结论，如果我们只检查除法到 N 的平方根，那么它将在非常短的时间内给出相同的结果。让我们看看上面方法的代码 -</p>
<pre class="brush:javascript;toolbar:false;">function isPrime(number){
   if(number == 1) return false
   var count = 0;
   for(var i = 1;i*i
<p>在上面的代码中，我们刚刚通过更改 for 循环的范围来更改之前的代码，因为现在它只会检查 N 个元素的第一个平方根，并且我们将计数增加了 2。</p>
<p>上述代码的时间复杂度为O(sqrt(N))，较好，这意味着我们可以使用该方法来查找给定范围内存在的素数的个数。</p>
<h2>L 到 R 范围内的素数个数</h2>
<h3>示例</h3>
<p>我们将在范围内实现之前给出的代码，并计算给定范围内的素数数量。让我们实现代码 -</p>
<pre class="brush:javascript;toolbar:false;">function isPrime(number){
   if(number == 1) return false
   var count = 0;
   for(var i = 1;i*i
<p>在上面的代码中，我们使用 for 循环遍历了从 L 到 R 的范围，并且在每次迭代时，我们都检查当前数字是否是质数。如果该数字是素数，那么我们就增加计数，最后打印该值。</p>
<p>上述代码的时间复杂度为 O(N*N)，其中 N 是 Range 中的元素数量。</p>
<h2>埃拉托色尼算法筛选</h2>
<h3>示例</h3>
<p>埃拉托斯特尼筛法算法工作效率很高，可以在 O(Nlog(log(N))) 时间内找到给定范围内的素数个数，与其他算法相比，速度非常快。筛子占用的空间是 O(N)，但这并不重要，因为时间非常有效。让我们看看代码，然后我们将转向代码的解释 -</p>
<pre class="brush:javascript;toolbar:false;">var L = 10
var R = 5000
var arr = Array.apply(null, Array(R+1)).map(Number.prototype.valueOf,1);
arr[0] = 0
arr[1] = 0

for(var i = 2;i
<p>在上面的代码中，我们看到了埃拉托斯特尼筛的实现。首先，我们创建了一个包含大小为 R 的数组，之后我们使用 for 循环遍历了该数组，并且对于每次迭代，如果当前数字不是 1，则意味着它不是素数，否则它是素数，并且我们已经删除了所有小于 R 且当前质数的倍数的数。然后我们创建了一个前缀数组，它将存储从 0 到当前索引的素数计数，并且可以在恒定时间内提供 0 到 R 范围内每个查询的答案。</p>
<h3>时间和空间复杂度</h3>
<p>上述代码的时间复杂度为 O(N*log(log(N)))，与 O(N*N) 和 O(N*(sqrt(N)) 相比要好得多）。与之前的代码相比，上述代码的空间复杂度更高，为 O(N)。</p>
<h2>结论</h2>
<p>在本教程中，我们了解了如何使用 JavaScript 编程语言查找给定范围内的素数个数。质数是恰好有两个完美约数的数字。 1 不是质数，因为它只有一个完美约数。我们已经看到了时间复杂度为 O(N*N)、O(N*sqrt(N)) 和 O(N*log(log(N))) 的三种方法。另外，前两种方法的空间复杂度为 O(1)，埃拉托色尼筛法的空间复杂度为 O(N)。</p>

Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南