用於計算範圍內素數的 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中文網其他相關文章！