資料結構
網路
關係資料庫管理系統 (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+ 瀏覽量
