数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学JavaScript 范围内素数计数程序
素数是指恰好只有两个因数的数。我们将介绍两种在给定范围内查找素数个数的方法。第一种是使用暴力法，这种方法的时间复杂度较高。然后我们将改进这种方法，并采用埃拉托斯特尼筛法来获得更好的时间复杂度。在本文中，我们将使用 JavaScript 编程语言来查找给定范围内素数的总数。
暴力法
在这种方法中，我们将首先学习如何判断一个数是否是素数，我们可以用两种方法来实现。一种方法的时间复杂度为 O(N)，另一种方法的时间复杂度为 O(sqrt(N))。
判断一个数是否为素数的直接方法
示例
首先，我们将遍历一个循环直到该数，并计算可以完美整除该数的数的个数，如果可以整除该数的数的个数不等于 2，则该数不是素数，否则该数是素数。让我们看看代码：
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（即我们可以找到可以整除给定数的数的范围）进行遍历，并计算出可以整除给定数的数的个数，并根据该个数打印结果。
上述代码的时间复杂度为 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 = 10
var R = 5000
var count = 0
for(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 的范围，并在每次迭代中检查当前数字是否为素数。如果该数字是素数，则我们将计数增加 1，最后打印该值。
上述代码的时间复杂度为 O(N*N)，其中 N 是范围内的元素个数。
埃拉托斯特尼筛法
示例
埃拉托斯特尼筛法以一种高效的方式工作，并在 O(Nlog(log(N))) 时间内找到给定范围内的素数个数，这比其他算法快得多。筛法占用的空间为 O(N)，但这并不重要，因为时间效率很高。让我们看看代码，然后我们将解释代码：
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<=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 的包含 1 的数组，之后我们使用 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)。
4K+ 浏览量
