1
$\begingroup$

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;
  }
$\endgroup$
2
$\begingroup$

Sorry, but you can’t just count loops, the number of loops is totally irrelevant.

If you count nested loops, that is slightly significant but can be very misleading.

You need to count how many iterations a loop performs. In the first example, the number of iterations is up to primes.length, which is around n / log n. In the second example, the number of iterations in the inner loop is less than n / 2i, and i grows quickly.

Add a counter to each function and see how often the inner loop gets executed.

PS. Let n = 1 billion, and print say every 100th prime added to primeVals. Then check how long it takes. The sieve will take a good time. But I can promise you, the “optimised” algorithm will be a lot more than ten times slower.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Normally a loop behaves linearly, but when you do interview problems they do not, so that threw me off. Not really a loop just a way to iterate numbers. $\endgroup$ – j.a. Feb 13 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.