freeCodeCamp Challenge Guide: Sum All Primes Update

Contributors
7

As promised, here is an annotated example showing the basic idea behind the Sieve of Eratosthenes based approaches. I am a C guy, so this is close(ish) to the way to get the best performance in C. I haven’t done a lot of performance analysis in JavaScript since high speed isn’t exactly what the language is know for. Memory management and optimization is so much easier in C.

Just the Function:

function sumPrimes(num) {
  // Bounds checking
  if (num <= 1)
    return 0;

  // Make boolean array of odd numbers
  const upper = Math.floor((num - 1)/2);
  const isPrime = Array(upper).fill(true); // 'Guess' all are prime

  // Mark multiples of each prime as false (not prime)
  const sqrtUpper = Math.floor((Math.sqrt(num) - 1)/2); // Done when i*i marked
  for (let i = 0; i <= sqrtUpper; ++i)
    // Check if number is multiple of any smaller odd number
    if (isPrime[i]) {
      // Loop bound values
      const prime = 2*i+3; // Note that number = index*2+3
      const primeSqaredIndex = 2*i*i + 6*i + 3; // Everything below prime*2 marked
      // Mark all multiples of this number as false (not prime)
      for (let j = primeSqaredIndex; j < upper; j+=prime)
        isPrime[j] = false;
    }

  // Count sum
  let sum = 2
  for (let i = 0; i < upper; ++i)
    if (isPrime[i])
      sum += 2*i+3;

  // Return
  return sum;
}

Full Demo Code:

Click Here for Code 
// ********************************************************************************
// Sieve of Eratoshenes sumPrimes demo and performance study
// ********************************************************************************

// --------------------------------------------------------------------------------
// Debug via console logging flag
// --------------------------------------------------------------------------------
const debug = false;

// --------------------------------------------------------------------------------
// Brief: Sum primes from 2 to num (inclusive)
//
// Inputs:
//  num - upper bound to sum primes (inclusive)
//
// Outputs:
//  sum - sum of primes from 2 to num (inclusive)
// --------------------------------------------------------------------------------
function sumPrimes(num) {
  if (debug) console.log("WARNING - DEBUGGING LOGGING WILL DECREASE PREFORMANCE");

  // Bounds checking
  if (num <= 1)
    return 0;

  // Make boolean array of odd numbers
  const upper = Math.floor((num - 1)/2);
  const isPrime = Array(upper).fill(true); // 'Guess' all are prime
  if (debug) console.log(" -- Upper: " + upper);

  // Mark multiples of each prime as false (not prime)
  const sqrtUpper = Math.floor((Math.sqrt(num) - 1)/2); // Done when i*i marked
  for (let i = 0; i <= sqrtUpper; ++i)
    // Check if number is multiple of any smaller odd number
    if (isPrime[i]) {
      // Loop bound values
      const prime = 2*i+3; // Note that number = index*2+3
      const primeSqaredIndex = 2*i*i + 6*i + 3; // Everything below prime*2 marked
      // Mark all multiples of this number as false (not prime)
      for (let j = primeSqaredIndex; j < upper; j+=prime)
        isPrime[j] = false;
    }
  if (debug) console.log(" -- isPrime: " + isPrime);

  // Count sum
  let sum = 2
  for (let i = 0; i < upper; ++i)
    if (isPrime[i])
      sum += 2*i+3;
  if (debug) console.log(" -- Sum: " + sum);

  // Return
  if (debug) console.log("END DEBUGGING OUTPUT");
  return sum;
}

// --------------------------------------------------------------------------------
// Performance testing
// --------------------------------------------------------------------------------
// Throw away first timing
sumPrimes(50000000)

// Test cases
const maxPower = 8;
const numRuns = 5;
for (let i = 0; i < maxPower; i++) {
  /// Log test case
  const num = 5*(10**i);
  console.log("Test Case: " + i)
  console.log(" Num: " + num)

  // Multiple runs
  let sum = 0;
  for (let j = 0; j < numRuns; j++) {
    // Log sub case
    console.log(" - Run: " + j)
    // Time execution
    // Note: could make cleaner and run stats with performance (need NodeJS)
    console.time("sumPrimes");
    sum = sumPrimes(num);
    console.timeEnd("sumPrimes");
  }

  // Output
  console.log("Result: " + sum + "\n")
}

// ********************************************************************************
Click Here for Repl Link

https://repl.it/repls/IncompatibleBitterNlp

Results:

Your code:

num =  5000
sumPrimes: 12.867ms
Result: 1548136

num = 500000
sumPrimes: 10696.653ms
Result: 9914236195

My code (pre optimization):

num = 5000
sumPrimes: 1.469ms
Result: 1548136

num =  500000
sumPrimes: 21.166ms
Result: 9914236195

I’m sure I can optimize this more, but I think that these results show what I mean when I said that your code will struggle with large values. Your code takes 831x longer with a 100x larger input while mine takes 14x longer with a 100x larger input.

(Note: performance measuring is a tricky thing. To do it correctly, I’d need to do multiple runs, take the average, and test over a wider range of values of num. As strange as it maybe sounds, 500000 is really too small to be a good test value. This performance testing is not exhaustive but more illustrative.)

If some of you JavaScript experts on the forum would like to comment, I am curious about how fast we could get this approach.

Click Here for Performance Discussion

EDIT 1:
I swapped

  let isPrime = [];
  for (let i = 3; i <= num; i+=2) // Increment by 2 for odds
    isPrime.push(true);

for

  let isPrime = Array((num-2)/2).fill(true);

which shaved some ms, especially on the high end. I suspected that my first approach was a bad way to make an array full of Booleans. Preallocation is the way to go though, at least in repl.it, as I’m seeing a 10x increase in timing if I don’t preallocate.

EDIT 2:
Swapping out

isPrime.length

for

const upper = isPrime.length

and referencing this in all of the loop bounds got another nice little performance increase.
Current:

num = 5000
sumPrimes: 1.274ms
Result: 1548136

num = 500000
sumPrimes: 17.913ms
Result: 9914236195

EDIT 3:
I am getting mixed results about if pre-incrementing vs post-incrementing matters for performance. Once upon a time it mattered for C/C++, but it doesn’t seem to matter in this case.

EDIT 4:
It seems that attempting to use Object.seal to indicate that the array properties won’t change actually substantially decreases performance. I wasn’t sure if there was any overhead in JavaScript assuming that the object might mutate.

EDIT 5:
Added improved performance testing.

Test Case: 0
 Num: 5
 - Run: 0
sumPrimes: 0.343ms
 - Run: 1
sumPrimes: 0.020ms
 - Run: 2
sumPrimes: 0.016ms
 - Run: 3
sumPrimes: 0.016ms
 - Run: 4
sumPrimes: 0.015ms
Result: 10

Test Case: 1
 Num: 50
 - Run: 0
sumPrimes: 0.031ms
 - Run: 1
sumPrimes: 0.019ms
 - Run: 2
sumPrimes: 0.016ms
 - Run: 3
sumPrimes: 0.019ms
 - Run: 4
sumPrimes: 0.023ms
Result: 328

Test Case: 2
 Num: 500
 - Run: 0
sumPrimes: 0.079ms
 - Run: 1
sumPrimes: 0.093ms
 - Run: 2
sumPrimes: 0.121ms
 - Run: 3
sumPrimes: 0.087ms
 - Run: 4
sumPrimes: 0.065ms
Result: 21536

Test Case: 3
 Num: 5000
 - Run: 0
sumPrimes: 0.640ms
 - Run: 1
sumPrimes: 56.682ms
 - Run: 2
sumPrimes: 0.699ms
 - Run: 3
sumPrimes: 1.603ms
 - Run: 4
sumPrimes: 0.732ms
Result: 1548136

Test Case: 4
 Num: 50000
 - Run: 0
sumPrimes: 6.654ms
 - Run: 1
sumPrimes: 0.574ms
 - Run: 2
sumPrimes: 0.568ms
 - Run: 3
sumPrimes: 0.705ms
 - Run: 4
sumPrimes: 0.590ms
Result: 121013308

Test Case: 5
 Num: 500000
 - Run: 0
sumPrimes: 6.009ms
 - Run: 1
sumPrimes: 6.195ms
 - Run: 2
sumPrimes: 5.148ms
 - Run: 3
sumPrimes: 5.031ms
 - Run: 4
sumPrimes: 65.059ms
Result: 9914236195

Test Case: 6
 Num: 5000000
 - Run: 0
sumPrimes: 115.162ms
 - Run: 1
sumPrimes: 128.219ms
 - Run: 2
sumPrimes: 183.558ms
 - Run: 3
sumPrimes: 173.827ms
 - Run: 4
sumPrimes: 120.101ms
Result: 838596693108

Test Case: 7
 Num: 50000000
 - Run: 0
sumPrimes: 2182.912ms
 - Run: 1
sumPrimes: 2236.097ms
 - Run: 2
sumPrimes: 2262.116ms
 - Run: 3
sumPrimes: 2226.781ms
 - Run: 4
sumPrimes: 2277.946ms
Result: 72619548630277

As expected, very small can be very expensive, relatively speaking. There is a drop off in efficiency for the last couple test cases, which is interesting. It looks like those switch over to using long integers, if I’m not mistaken.

EDIT 6:
To be perfectly honest, this is overkill for an answer at this point. I just sort of got carried away doing some playing with performance because its fun. I’m still curious about if anyone else on the forum has performance tips in this case, but I’ll call this good enough on my end. It’s my understanding that in a case like this pure for loops are faster than built in language features like maps and the like because they are easier for JavaScript to optimize, but I’m really not sure.

EDIT 7:
Ok, I couldn’t help myself. Dropped the separate summing loop and instead summed as I went. Its a nice performance boost.

EDIT 8:
I would like to note that I beat the guide solution #1 both in terms of time to solution and memory used (the two are linked). Saving an array of the primes isn’t useful in this case and it causes “JavaScript heap out of memory” type problems sooner.

EDIT 9:
Better performance if you only check for primes up to the square root of the target number. You have to add back the sum array, but it’s worth it.

1 Like