freeCodeCamp Challenge Guide: Sum All Primes Update

Contributors
1

I checked out the guide: freeCodeCamp Challenge Guide: Sum All Primes and the solutions it included and it seems so complicated and hard to understand.

If you think about the prime numbers. You realize that 2 is the only even prime number. All other prime numbers are odd. So you don’t need to generate something like [2, 3, 4, 5, 6, 7, …]. You only need to generate an array full of odd numbers, like this [3, 5, 7, 9, …].

Then you filter the array full of the odd numbers to see if they are able to be divided by every prime odd number with no remainder and push the odd number with the remainder to the prime array and then unshift “2” to the beginner of the array and sum all the prime array up.

Here’s my solution:

function sumPrimes(num) {
  let primeArr = [];
  for(let i = 3; i <= num; i+=2){
    if(primeArr.every((prime) => i%prime !=0)) {
      primeArr.push(i);
    }
  }
  primeArr.unshift(2);
  return primeArr.reduce((a, b) => a + b);
}

console.log(sumPrimes(10));
3 Likes
2

You do have an easy to read solution, though it will struggle to perform as well as the Seive based solutions as the bound grows.

3

Well, it would be nice if anyone post a solution that is a better solution (improvement) and clear to understand here :slight_smile: I’m looking forward to it.

4

I could probably polish up one tomorrow. The core idea is pretty close to your filter, actually. You make a Boolean array representing all odd numbers from 3 to num and ‘guess’ they are all prime. You then start at 3 and flag all multiples of three as non prime. Then you move to the next prime and again flag multiples as non prime. Repeat until you reach the end of the array. Then you have a Boolean array with all numbers that aren’t multiples left marked as prime.

In this approach, the number of values you mark as not prime reduces as you go, while with a filter the number of checks you make steadily increases.

5

Your solution is fine for small #s & good job for recognizing the pattern.

If you’re looking for improvements then you could improve drastically on time complexity and space complexity.

For time complexity improvements, you’re going to have to use maths.
For space complexity I’m going to highly recommend you look into what Javascript generators are.

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
8

It’s damn fast, but unfortunately it produces incorrect result. Maybe that’s the reason why it’s so fast?

9

Which result is off? Did I miss an edge case somewhere?

10

Woops, I see it. It’s the good old ceil when I meant floor. It works now.

11

Hello, I come up with a solution quite similar to yours in concept…I just check for prime number as soon as they get generated (they are prime if they do not have module zero when divided for any of the lower numbers), and add them in a variable:

function sumPrimes(num) {
  let i = 2;
  let nums = [];
  let sum = 0;
  while (i <= num){
    if (nums.every(item => i % item != 0)) {
      sum += i;
    }
    nums.push(i);
    i++;
  }
  return sum;
}

I’m not sure about the overall efficiency…but the logic seems pretty clear to me :grinning:
How could I suggest an update to the existing solutions?

12

Hi @paluigi!

Welcome to the forum!

If you are interested in making a suggestion for the guide, please create a new post in the #contributors section.

For contributions, please wrap your solution within :

[details]
```
code goes here...
```
[/details]

Also, provide all of the necessary code to pass the challenge.

Also, when you enter a code block into a forum post, please precede it with a separate line of three backticks and follow it with a separate line of three backticks to make it easier to read.

You can also use the “preformatted text” tool in the editor ( </> ) to add backticks around text.

Pre-formatted-text
Pre-formatted-text1356×380 401 KB

See this post to find the backtick on your keyboard.
Note: Backticks (`) are not single quotes (’).

1 Like