用于计算范围内素数的 JavaScript 程序-js教程-PHP中文网

用于计算范围内素数的 JavaScript 程序

质数是恰好有两个完美约数的数字。我们将看到两种查找给定范围内素数数量的方法。第一种是使用暴力法，这种方法时间复杂度有点高。然后我们将改进这个方法，并采用埃拉托色尼筛法算法以具有更好的时间复杂度。在本文中，我们将使用 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 = 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 的范围，并且在每次迭代时，我们都检查当前数字是否是质数。如果该数字是素数，那么我们就增加计数，最后打印该值。

上述代码的时间复杂度为 O(N*N)，其中 N 是 Range 中的元素数量。

埃拉托色尼算法筛选

示例

埃拉托斯特尼筛法算法工作效率很高，可以在 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 的数组，之后我们使用 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 程序的详细内容。更多信息请关注PHP中文网其他相关文章！