質數是恰好有兩個完美約數的數字。我們將看到兩種查找給定范圍內素數數量的方法。第一種是使用暴力法，這種方法時間復雜度有點高。然后我們將改進這個方法，并采用埃拉托色尼篩法算法以具有更好的時間復雜度。在本文中，我們將使用 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 程序的詳細內容，更多請關注www.92cms.cn其它相關文章！
