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.