What is the complexity of my implementation of the 'Eratosthenes Sieve' algorithm, how to improve it?

Question

What is the complexity of my implementation of the 'Eratosthenes Sieve' algorithm, how to improve it?

Help us understand the complexity of the algorithm. I tried to implement the 'Sieve of Eratosthenes'.

P.S. As far as I understand, the first loop, despite continue, has a complexity of sqrt(N), and the nested log(N), it turns out the final sqrt(N)*log(N)?
P. P. S. I would appreciate an example with complexity log(log(N)).

The function code is below:

function filterOut(number) {
    var tempArray = new Array(number);
    var finalArray = [];
    var limit = Math.sqrt(number);
    for(var i = 2; i < limit; i++) {
        if(tempArray[i] != undefined) continue;
        else {
            for(var j=i; j*i < number; j++) {
                tempArray[j*i] = 0;
            }
        }
    }
    for(var i = 2; i < number; i++) {
        if(tempArray[i] != 0) finalArray.push(i);
    }
    return finalArray;
}

11

алгоритм javascript сложность

Author: Danis, 2017-11-27

Source

3 answers

score 1 · Answer 1

To reduce the complexity of the algorithm, exclude even numbers. The point in practical problems is to add them to the sieve, if only for demonstration for educational purposes. And it makes sense to store it in the form of an int array, it is more reasonable in a bit array (you significantly save memory and the engine resource for its allocation). Below is a generator using a sieve.

function Base(size) {
  this.arr = new Uint32Array(size);
}

Base.prototype.Add = function (num) {
  this.arr[num >> 5] |= 1 << (num & 31);
};

Base.prototype.isSet = function (num) {
  return (this.arr[num >> 5] & (1 << (num & 31))) !== 0;
};

let Max = 472882240;
let base = new Base((Max >> 5) + 1);

function init() {
  for (let i = 3; i < 21800; i += 2) {
    if (base.isSet(i)) 
      continue;
    for (let x = i + i; x <= Max; x += i) {
      base.Add(x);
    }
  }
}

class Primes {

  static *stream() {
    let num = 0;
    yield 2;

    for (let i = 3; i <= Max; i += 2)
      if (!base.isSet(i)) {
        yield i;
      }

  }

}

init();

score -1 · Answer 2

I propose this implementation of the algorithm "Sieve of Eratosthenes" in javascript:

UPD: fixed the code based on the discussion in the question https://stackoverflow.com/questions/54614967/algorithm-sieve-of-eratosthenes-by-javascript

console.time('exec');
var arr = fn(Math.pow(10, 5));

function fn(n) {
  var arr = Array.apply(null, {
    length: n + 1
  }).map(function(_, i) {
    return i > 1;
  });
  var base = 2;
  while (Math.pow(base, 2) < n) {
    var counter = 2;
    while (counter * base <= n) {
      arr[counter * base] = false;
      do {
        counter++;
      } while (!arr[base]);
    }
    do {
      base++;
    } while (!arr[base]);
  }
  return arr;
}
console.timeEnd('exec');
console.log('array length: ' + arr.length);

// show result
/*
arr.forEach(function(item, index) {
  if (item) {
    console.log(index);
  }
});
*/

score -3 · Answer 3

Detailed solution:

function eratosthenes(n) {
    var array = [], upperLimit = Math.sqrt(n), output = [];

    // Создаем массив от 2 до n-1
    for (var i = 0; i < n; i++) {
        array.push(true);
    }

    // Удаляем простые числа начиная с 2, 3, 5 ...
    for (var i = 2; i <= upperLimit; i++) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i) {
                array[j] = false;
            }
        }
    }

    // Результирующий массив
    for (var i = 2; i < n; i++) {
        if(array[i]) {
            output.push(i);
        }
    }

    return output;
};

console.log(eratosthenes(100));

I didn't know what the sieve of Eratosthenes was, but I solved the problem. Enjoy it!