质数是恰好有两个完美约数的数字。我们将看到两种查找给定范围内素数数量的方法。第一种是使用暴力法，这种方法时间复杂度有点高。然后我们将改进这个方法，并采用埃拉托色尼筛法算法以具有更好的时间复杂度。在本文中，我们将使用 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 范围内找到能整除给定数字的数字，并得到有多少个数字能整除给定数字，并打印结果以此为基础。
上述代码的时间复杂度为 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。上述代码的时间复杂度为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 程序的详细内容。