質(zhì)數(shù)是恰好有兩個(gè)完美約數(shù)的數(shù)字。我們將看到兩種查找給定范圍內(nèi)素?cái)?shù)數(shù)量的方法。第一種是使用暴力法，這種方法時(shí)間復(fù)雜度有點(diǎn)高。然后我們將改進(jìn)這個(gè)方法，并采用埃拉托色尼篩法算法以具有更好的時(shí)間復(fù)雜度。在本文中，我們將使用 JavaScript 編程語言查找給定范圍內(nèi)的素?cái)?shù)總數(shù)。
暴力法
首先，在這個(gè)方法中，我們將學(xué)習(xí)如何找到一個(gè)數(shù)字是否是素?cái)?shù)，我們可以通過兩種方法找到它。一種方法的時(shí)間復(fù)雜度為 O(N)，另一種方法的時(shí)間復(fù)雜度為 O(sqrt(N))。
判斷一個(gè)數(shù)是否為素?cái)?shù)的直接法
示例
首先，我們會(huì)進(jìn)行for循環(huán)，直到得到一個(gè)數(shù)，并統(tǒng)計(jì)能整除該數(shù)的數(shù)，如果能整除該數(shù)的數(shù)不等于2，則該數(shù)不是質(zhì)數(shù)，否則number 是質(zhì)數(shù)。讓我們看看代碼 –
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")
}
登錄后復(fù)制
在上面的代碼中，我們從 1 到 number 進(jìn)行遍歷，在 number 范圍內(nèi)找到能整除給定數(shù)字的數(shù)字，并得到有多少個(gè)數(shù)字能整除給定數(shù)字，并打印結(jié)果以此為基礎(chǔ)。
上述代碼的時(shí)間復(fù)雜度為 O(N)，檢查每個(gè)數(shù)字是否為素?cái)?shù)將花費(fèi) O(N*N)，這意味著這不是一個(gè)好的檢查方法。
數(shù)學(xué)方法
我們知道，當(dāng)一個(gè)數(shù)完全整除另一個(gè)數(shù)時(shí)，商也是一個(gè)完全整數(shù)，也就是說，如果一個(gè)數(shù) p 可以被一個(gè)數(shù) q 整除，則商為 r，即 q * r = p。 r 也可以將數(shù) p 與商 q 整除。因此，這意味著完美除數(shù)總是成對出現(xiàn)。
示例
通過上面的討論，我們可以得出結(jié)論，如果我們只檢查除法到 N 的平方根，那么它將在非常短的時(shí)間內(nèi)給出相同的結(jié)果。讓我們看看上面方法的代碼 –
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")
}
登錄后復(fù)制
在上面的代碼中，我們剛剛通過更改 for 循環(huán)的范圍來更改之前的代碼，因?yàn)楝F(xiàn)在它只會(huì)檢查 N 個(gè)元素的第一個(gè)平方根，并且我們將計(jì)數(shù)增加了 2。
上述代碼的時(shí)間復(fù)雜度為O(sqrt(N))，較好，這意味著我們可以使用該方法來查找給定范圍內(nèi)存在的素?cái)?shù)的個(gè)數(shù)。
L 到 R 范圍內(nèi)的素?cái)?shù)個(gè)數(shù)
示例
我們將在范圍內(nèi)實(shí)現(xiàn)之前給出的代碼，并計(jì)算給定范圍內(nèi)的素?cái)?shù)數(shù)量。讓我們實(shí)現(xià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;
}
}
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);
登錄后復(fù)制
在上面的代碼中，我們使用 for 循環(huán)遍歷了從 L 到 R 的范圍，并且在每次迭代時(shí)，我們都檢查當(dāng)前數(shù)字是否是質(zhì)數(shù)。如果該數(shù)字是素?cái)?shù)，那么我們就增加計(jì)數(shù)，最后打印該值。
上述代碼的時(shí)間復(fù)雜度為 O(N*N)，其中 N 是 Range 中的元素?cái)?shù)量。
埃拉托色尼算法篩選
示例
埃拉托斯特尼篩法算法工作效率很高，可以在 O(Nlog(log(N))) 時(shí)間內(nèi)找到給定范圍內(nèi)的素?cái)?shù)個(gè)數(shù)，與其他算法相比，速度非?？?。篩子占用的空間是 O(N)，但這并不重要，因?yàn)闀r(shí)間非常有效。讓我們看看代碼，然后我們將轉(zhuǎ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);
登錄后復(fù)制
在上面的代碼中，我們看到了埃拉托斯特尼篩的實(shí)現(xiàn)。首先，我們創(chuàng)建了一個(gè)包含大小為 R 的數(shù)組，之后我們使用 for 循環(huán)遍歷了該數(shù)組，并且對于每次迭代，如果當(dāng)前數(shù)字不是 1，則意味著它不是素?cái)?shù)，否則它是素?cái)?shù)，并且我們已經(jīng)刪除了所有小于 R 且當(dāng)前質(zhì)數(shù)的倍數(shù)的數(shù)。然后我們創(chuàng)建了一個(gè)前綴數(shù)組，它將存儲(chǔ)從 0 到當(dāng)前索引的素?cái)?shù)計(jì)數(shù)，并且可以在恒定時(shí)間內(nèi)提供 0 到 R 范圍內(nèi)每個(gè)查詢的答案。
時(shí)間和空間復(fù)雜度
上述代碼的時(shí)間復(fù)雜度為 O(N*log(log(N)))，與 O(N*N) 和 O(N*(sqrt(N)) 相比要好得多）。與之前的代碼相比，上述代碼的空間復(fù)雜度更高，為 O(N)。
結(jié)論
在本教程中，我們了解了如何使用 JavaScript 編程語言查找給定范圍內(nèi)的素?cái)?shù)個(gè)數(shù)。質(zhì)數(shù)是恰好有兩個(gè)完美約數(shù)的數(shù)字。 1 不是質(zhì)數(shù)，因?yàn)樗挥幸粋€(gè)完美約數(shù)。我們已經(jīng)看到了時(shí)間復(fù)雜度為 O(N*N)、O(N*sqrt(N)) 和 O(N*log(log(N))) 的三種方法。另外，前兩種方法的空間復(fù)雜度為 O(1)，埃拉托色尼篩法的空間復(fù)雜度為 O(N)。
以上就是用于計(jì)算范圍內(nèi)素?cái)?shù)的 JavaScript 程序的詳細(xì)內(nèi)容，更多請關(guān)注www.92cms.cn其它相關(guān)文章！
