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

## Question:

Help to understand the complexity of the algorithm. Tried to implement the 'Sieve of Eratosthenes'.

PS As far as I understand the first loop despite `continue` has complexity `sqrt(N)` , and nested `log(N)` , the final `sqrt(N)*log(N)` is obtained?
PPS I would appreciate an example with `log(log(N))` complexity.

Function code 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;
}
``````

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

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

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) {
}
}
}

class Primes {

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

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

}

}

init();
``````
Scroll to Top