# Is the sieve an improvement for prime finding over an optimized algorithm?

I don't think it is, as you have to loop through each set multiple times at least.

implementation of sieve in JS - in the answer at the bottom. The link shows a 10X improvement using sieve.

In this case it is faster b.c. the function changes the integers to bits and is working with bits instead of integers.

But if you look at the structure of the code it has 3 loops. An optimized non sieve version has only 2 loops.

For example here is an optimized algorithm:

function findPrimes(n){
const primes = [2];
label: for(let i = 3; i <= n; i += 2){
for(let j = 0; j < primes.length; j++){
if(i % primes[j] === 0) {
continue label;
}
}
primes.push(i);
}
return primes;
}


and here is the sieve method using bit-wise operations.

  "sieve": function sieveOfEratosthenes(n) {
var sieve = new Int32Array(Math.ceil((n + 1) / 64)).fill(-1);
var primeVals = [2];

for (var i = 3; i * i <= n; i += 2) {
if (sieve[i >> 6] & (1 << (i >> 1 & 31))) {
primeVals.push(i);

for (var j = i * i; j <= n; j += i + i) {
sieve[j >> 6] &= ~(1 << (j >> 1 & 31));
}
}
}

while (i <= n) {
if (sieve[i >> 6] & (1 << (i >> 1 & 31))) {
primeVals.push(i);
}
i+=2;
}
return primeVals;
}