查找10001素數 - 歐拉項目

我正在嘗試查找第10,001個質數。我已經看過人們編寫的其他代碼，但我不太明白它的意思。我用JavaScript編寫了一些代碼，我嘗試使用Eratosthenes的Sieve。我不確定問題是什麼。它看起來應該正常工作，但我得到了錯誤的答案。查找10001素數 - 歐拉項目

var compute = function() { 
var prime = [2,3,5,7,11,13,17,19]; 
for(var i=20; i<=80000;i++) { 
if(i%2!==0 && i%3!==0 && i%5!==0 && i%7!==0 && i%11!==0 && i%13!==0 && i%17!==0 &&  i%19!==0) { 
prime.push(i); 
    } 
} 
console.log(prime[10000]); 
}; 

compute();

來源

2013-04-18 TGarr

31 * 37 = 1147，所以1147不是素數，但是您的條件會認爲它是素數。 – Passerby 2013-04-18 04:06:52

一個簡單的Google搜索：http://rosettacode.org/wiki/Sieve_of_Eratosthenes#JavaScript – jfriend00 2013-04-18 04:09:19

這可以通過僅檢查以1 3 7或9結尾的數字來優化，而不是按1遞增。 – Klik 2013-04-18 04:09:55

這是一個簡單的方法，但要找到萬分之一

（或在某些機器甚至十萬分之一）

你需要超時砍它，

或出貨關閉webworker以防止鎖定。

你只需要檢查素因子，你收集它們，

，因爲每一個數字或者是素數

的產品或者其本身就是黃金。

function nthPrime(nth){ 
    var P= [2], n= 3, div, i, limit,isPrime; 
    while(P.length<nth){ 
     div= 3, i= 1; 
     limit= Math.sqrt(n)+1; 
     isPrime= true; 
     while(div<limit){ 
      if(n%div=== 0){ 
       isPrime= false; 
       div= limit; 
      } 
      else div= P[i++] || div+ 2; 
     } 
     if(isPrime) P.push(n); 
     n+= 2; 
    } 
    return P[P.length-1]; 
}

alert（nthPrime（10001））;

來源

2013-04-18 04:28:50 kennebec

你的代碼完美無缺。我試圖分解它來試圖理解它，但我無法做到。第二個while循環讓我絆倒。無論如何，我會評分你的答案。 – TGarr 2013-04-18 05:06:22

@TGarr這是一個可以找到所有素數的解決方案。要檢查一個數字「n」是否爲素數，你只需要確保它不能被每個素數{{p | p <= sqrt（n）}'這就是這個解決方案所做的。 – FrankieTheKneeMan 2013-04-18 11:01:39

您的代碼沒有實現Eratosthenes篩。你必須執行以下步驟（來源：http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）：

創建連續整數的列表，從2到n：（2，3，4，...， N）。
最初，讓p等於2，第一個素數。
從p開始，以p爲增量向上計數，並在列表中將這些數字中的每一個標記爲大於p本身的。這些將是p：2p， 3p，4p等的倍數;注意其中一些可能已經被標記。
查找列表中未標記的第一個大於p的數字。如果沒有這樣的號碼，請停下來。否則，設p現在等於這個號（這是下一個素數），如果你想找到第一萬零一素數從第3步

重複，你要選擇足夠大ň，從而使結果數組至少包含10001個元素，然後選擇10001st元素作爲結果。

來源

2013-04-18 04:17:07

是的，我真的不理解如何做到這一點。再次通過Eratosthenes的Sieve再讀也沒有幫助。必須有一個較簡單的答案。 – TGarr 2013-04-18 04:34:10

查找10001素數 - 歐拉項目

回答

相關問題