var talet = 20;
var primtal = true;
var test = 2;
while (test < talet)
{
if (talet % test == 0) { primtal = false; }
test = 1;
}
if (talet == 1)
alert("false")
else alert(primtal)很多 hof 這是用瑞典文寫的 = 數字 ptimtal = 素數
uj5u.com熱心網友回復：
該演算法效率太低，無法檢查較大素數的素數，因為它在線性時間 O(n) 中運行，檢查除數為止。對于具有 k 位數字的二進制數，這會產生 O(2^k) 的 k 中最壞情況的運行時指數，這非常糟糕并且即使對于相當“小”的數字（例如1e12.
如果您需要某個范圍內的所有素數，請查看Eratosthenes 篩。
如果您只想檢查選定的大數的素數，您可能需要查看概率Miller-Rabin 素數檢驗。然后，您可以通過生成大亂數并使用 Miller-Rabin 檢驗檢查它們來生成大素數。
你的簡單篩子可以通過只檢查除數到數字的平方根來優化；您也可以在找到除數后立即退出回圈：
var talet = 10000;
var primtal = true;
for (let divisor = 2; divisor <= Math.sqrt(talet); divisor )
{
if (talet % divisor == 0) { primtal = false; break; }
}
if (talet == 1) primtal = false
alert(primtal)這將漸近運行時間提高到 O(sqrt n)，或者根據 k O(sqrt 2^k) = O(2^k^0.5) = O(2^(0.5k))。
uj5u.com熱心網友回復：
這里可以做兩個優化
- 只需檢查從 2 到原始數字平方根的數字
- 只需檢查 2 和奇數，要獲得更多改進，您只能檢查
6k 1and形式的數字6k - 1。
function isPrime(number) {
if(number === 1 || number % 2 === 0)
return false;
for(let i = 3; i <= Math.sqrt(number); i = 2) {
if(number % i === 0)
return false;
}
return true;
}
uj5u.com熱心網友回復：
提高時間復雜度的一種方法是僅在目標數的 square_root 之前測驗潛在的除數。
因此，改進的第 1 步：
const sqrt = Math.sqrt(talet);
const test = 2;
while(test < sqrt){
if(talet % test == 0){
primtal = false;
break; //will jump out of the loop
}
}
現在，進一步改進您的代碼取決于您需要做什么。您只需要計算一個數字或多個數字的素數嗎？
如果你只需要計算一個數字，那么這個方法是正確的。如果您需要計算許多數字的素數，那么您可能需要計算素數陣列。并且僅測驗該陣列中的除數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/478665.html
標籤：javascript
上一篇：如何在打字稿中匯入嵌套介面