資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學使用埃拉託斯特尼篩法查詢素數 JavaScript
在這個問題陳述中，我們的目標是應用埃拉託斯特尼篩法演算法，藉助 Javascript 功能找出素數。因此，在我們的程式中，我們將實現一個函式來查詢小於給定限制的素數。
理解問題陳述
問題陳述是在 Javascript 中編寫一個函式，該函式將用於查詢小於給定數字的素數。為了實現此函式，我們將使用埃拉託斯特尼篩法演算法。
什麼是埃拉託斯特尼篩法演算法？
埃拉託斯特尼篩法是一種簡單且經典的演算法，用於查詢小於給定範圍的所有素數。此演算法透過定義從 2 到給定範圍的所有數字的列表，然後迭代地將每個素數的倍數標記為非素數來工作。此過程將持續到所有素數都被識別為止。
此演算法是查詢素數的有效演算法，時間複雜度為 O(n log n)。因此，可以說這種方法比檢查每個數字的素性的蠻力技術快得多。
給定問題的實現
為了實現此演算法，我們將建立一個大小為 n+1 的布林陣列，其中每個索引代表從 0 到 n 的數字。陣列中的所有元素最初都設定為 true。這將表示每個數字都是素數。設定為 false 的前兩個元素 0 和 1，因為它們不是素數。
之後，從第一個素數 2 開始，演算法將遍歷陣列，並將所有倍數標記為合數，方法是將其在陣列中的值設定為 false。現在，演算法將移動到下一個未標記的數字，並重復此過程，直到找到所有素數。
最後，演算法將遍歷陣列並收集值為 true 的所有索引。這表示它們是素數。
演算法
步驟 1 − 建立一個函式 generatePrimes 來查詢小於 n 個數字的素數。這裡 n 是傳遞給函式的引數。
步驟 2 − 建立一個大小為 n+1 的陣列，此陣列為布林型別，並將所有值初始化為 true。
步驟 3 − 遍歷從 2 到 n 的平方根的陣列。並檢查當前數字是否為素數，這意味著值為 true，然後遍歷其所有倍數直到 n，並將它們在陣列中的值設定為 false。
步驟 4 − 再次遍歷從 2 到 n 的陣列，並將所有素數新增到結果陣列中。
步驟 5 − 返回素數的結果陣列，並在螢幕上顯示示例用法。
演算法程式碼
function sieveOfEratosthenes(n) {
// Create a boolean array of size n+1
let primes = new Array(n + 1).fill(true);
// Set first two values to false
primes[0] = false;
primes[1] = false;
// Loop through the elements
for (let i = 2; i <= Math.sqrt(n); i++) {
if (primes[i]) {
for (let j = i * i; j <= n; j += i) {
primes[j] = false;
}
}
}
let result = [];
// Loop through the array from 2 to n
for (let i = 2; i <= n; i++) {
if (primes[i]) {
result.push(i);
}
}
return result;
}
console.log("All prime numbers up to 20");
console.log(sieveOfEratosthenes(20));
複雜度
建立的函式所花費的時間為 O(n log log n)，其中 n 是布林陣列的大小。該演算法從 2 迭代到 n 的平方根，並將每個素數的所有倍數標記為合數。迴圈迭代次數等於 n log log n，因此結果時間複雜度將為 O(n log log n)。因此，此演算法對於查詢素數非常有效。空間複雜度為 O(n)。
結論
埃拉託斯特尼篩法是一種查詢素數的系統方法。它透過查詢小於給定限制的所有非素數，並將它們標記為合數來工作。因此，剩餘的數字將是素數。此演算法對於小型到中型數字特別有效，並且易於在程式碼中實現。
1K+ 次瀏覽
