Why does my sieve not perform well for finding primes?

Question

I wrote two prime finder functions and the sieve only performs about 10% better. I'm using two optimizations for the simple version.

• Don't check even numbers
• Only check up to the square root or j * j <= i. ( equivalent )

and one optimization for the sieve version

• Only check up to the square root or i * i <= n. ( equivalent )

What optimizations can I add to the sieve?

My sieve is pretty slow. I don't want to do a bitwise implementation yet, I want to understand if this implementation offers any benefits.

Or if I missed an implementation point.

The inner for loop in the pseudocode here looks interesting / odd

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

I don't know how to interpret it. (update: the OP seems to indicate in the comments that it was an issue with incorrect formatting after copy-pasting the pseudocode from Wikipedia, and with the corrected formatting it is clear now)

Here it is:

algorithm Sieve of Eratosthenes is:

input: an integer n > 1.
output: all prime numbers from 2 through n.

let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n do
    if A[i] is true
        for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
            A[j] := false

return all i such that A[i] is true. 

// prime-2
// 2 optimizations - odds and square root
function prime2(n){
  const primes = [2];
  not_prime: for(let i = 3; i < n; i += 2){
    for(let j = 2; j * j <= i; j++){
      if(i % j === 0){
        continue not_prime;
      }
    }
    primes.push(i);
  }
  return primes;
}

// prime-3
// sieve implementation
function prime3 (n) {
  const primes = [];
  const sieve = (new Array(n)).fill(true);
  for (let i = 2; i * i <= n; i += 1) {
    if (sieve[i]) {
      for (let j = i + i; j < n; j += i) {
        sieve[j] = false;
      }
    }
  }
  makePrimes(sieve, primes, n);
  return primes;
};
function makePrimes(sieve, primes, n){
  for (let i = 2; i < n; i++) {
    if(sieve[i]) {
      primes.push(i);
    }
  }
}

Answer 1

What you see is an expression of the differences in theoretical run time complexities, i.e. the true algorithmic differences between the two algorithms.

Optimal trial division sieve's complexity is O(n^1.5/(log n)²)^(*) whereas the sieve of Eratosthenes' complexity is O(n log log n).

According to the empirical run time figures posted by Scott Sauyet in the comments,

   1e6      279ms      36ms
   1e7     6946ms     291ms
   -------------------------
   n^       1.40       0.91

the empirical orders of growth are roughly ~n^1.4 and ~n in the measured range, which is a good fit.

So your genuine sieve does perform well. The trial division sieve performs as expected. The algorithmic nature of a code will always beat any presence or absence of any secondary optimizations, if we increase the problem size enough.

And comparing performances by measuring them at just one problem-size point is never enough. So even if you see just 10% difference over the "simpler one", if you test at bigger sizes, the difference will be bigger.

---

If you want some pointers about what can be further improved in your code, do note that you start the inner loop from i+i instead of from i*i, for starters.

Another common optimization is to special-case 2, start from 3 and increment the candidates by 2 and use the inner loop increment of 2*i instead of just i, to achieve instant 2x speedup. This is the simplest form of wheel factorization optimization, which can be further applied, with diminishing returns though for each additional prime. But using 2-3-5-7 is common and should give about another 2x speedup, if memory serves.

Last but not least, make it segmented.

---

^(*) that's π(n)* π(√n) coming from primes, and no more than that, from the composites.