Решето Эратосфена на JavaScript


Я нашла этот способ, довольно трудно получить для новичка вроде меня, но я пытался сделать все возможное, и вот что я придумал.

Это хороший код относительно производительности? Что-то не так с ним?

var notPrime = [] ;
var prime = [] ;

var n = prompt("Enter n: ");

for(var i = 2 ; i < n ; i++ ){

    if(notPrime.indexOf(i) != -1){              
        continue;
    }   

    for(var j = i ; i <= j ; j++){
        if((i * j) < n){
            notPrime.push(i*j);
        } else {
            break;
        }
    }
    prime.push(i);
}

for(var f in prime){
    console.log(prime[f]);
}


Комментарии
1 ответ

Допустим, что есть комната для улучшения. ;)


В строке метод возвращает строку, но вы хотите номер, так что вы должны разобрать строку:

var n = parseInt(prompt("Enter n: "), 10);


С помощью метода indexOf на массив медленно. Вместо того, чтобы все не-простых чисел в ведро и рылся в нем, вы должны использовать массив, содержащий значения типа boolean, где индекс-номер и значений говорит вам, если это премьер или нет.

Доступ к массиву по индексу за O(1) операция, в то время как поиск значения в массиве за o(n) в эксплуатацию. Как N растет, этот код будет медленнее и медленнее, чем дольше вы дайте ему поработать.

Как вы толкаете большое дубликат номера-простые числа в массив, массив логических значений будет использовать около 70% меньше памяти, несмотря на праймы и занимает место в нем.


Этот цикл является довольно бессмысленно:

for(var j = i ; i <= j ; j++){

Условие никогда не будет ложным. Вы должны вместо этого использовать Я * й < N в состоянии вырваться из цикла:

for(var j = i; i * j < n; j++){
notPrime[i * j] = true;
}


Редактировать:

Вы все еще используете массив в качестве своего рода коллекция. Вы должны установить все значения в true при запуске, а затем установить все простые числа в false. Этот код (на основе алгоритма здесь) примерно в пять раз быстрее:

var n = parseInt(prompt("Enter n: "), 10);
var i, j;
var prime = new Array(n);
for (i = 2; i < n ; i++) prime[i] = true;

for (i = 2; i * i < n ; i++) {
if (prime[i]) {
for (j = 0; i * i + i * j < n ; j++) {
prime[i * i + i * j] = false;
}
}
}

var cnt = 0;
for (i = 2 ; i < n ; i++) {
if (prime[i]){
console.log(i);
}
}

5
ответ дан 13 октября 2011 в 04:10 Источник Поделиться