Поиск 10001st Prime Number - Project Euler

Question

Я пытаюсь найти 10 001-е число простых чисел. Я просмотрел другой код, написанный людьми, но я не совсем понимаю, что это значит. Я написал код в JavaScript, в котором я пытался использовать Sieve Of Eratosthenes. Я не уверен, в чем проблема. Похоже, что он должен работать правильно, но я получаю неправильный ответ.

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(); 

Answer 1

Это простой метод, но найти миллионной

(или даже сто тысячный в некоторых машинах)

вам необходимо измельчить с тайм-ауты,

или отправить его чтобы веб-сайт не задерживался.

Вам нужно всего лишь проверить простые делители, как вы собираете их,

поскольку каждое число либо произведение простых чисел

или сам премьер.

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]; 
} 

оповещения (nthPrime (10001));

Answer 2

Ваш код не использует сито Eratosthenes. Вы должны выполнить следующие шаги (источник: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes):

1. Создать список последовательных целых чисел от 2 до п: (2, 3, 4, ..., п ).
2. Первоначально пусть p равно 2, первое простое число.
3. Начиная с p, подсчитывайте с шагом p и отметьте каждое из этих номеров больше, чем p в списке. Они будут кратными p: 2p, 3p, 4p и т. Д .; обратите внимание, что некоторые из них, возможно, уже отмечены.
4. Найдите первое число, большее чем p, в списке, который не отмечен. Если такого номера не было, остановитесь. В противном случае, пусть р теперь составляет этот номера (который является следующим простым), и повторите процедуру с шага 3.

Если вы хотите найти 10001st простого числа, вы должны выбрать достаточно большим п, так что результирующий массив включает в себя по меньшей мере 10001 элементов, а затем в качестве результата выбирает 10001-й элемент.