AlgoDaily 18: Sum All Primes
https://algodaily.com/challenges/sum-all-primes
I remember there’s an algorithm called the Sieve of Eratosthenes for finding prime numbers up to a limit, which seems like it would be useful here.
To apply the Sieve of Eratosthenes, you first allocate an object with each
integer up to n as the keys.
You then iterate on integers up to $\sqrt{n}$. In other words, keep iterating on
integers p until p * p would be more than n. E.g. if n = 25, then the
iteration should stop at 5, because 5 * 5 = 25.
At each iteration, if that number has not yet been marked as not-prime, you
start at the square of it (p * p) and then iterate from there in increments of
p, marking all those numbers as not-prime. In other words, you start from
p * p and mark all multiples of p as not-prime.
Finally, rather than “marking as not-prime”, you can actually just delete that key from the object, then return the remaining keys as the primes at the end.
function sieveOfEratosthenes(n) {
const primes = {};
// Fill the object with all numbers 2..n
for (let i = 2; i <= n; i++) {
primes[i] = true;
}
// Iterate on integers 2..sqrt(n)
for (let p = 2; p * p <= n; p++) {
if (primes[p] === true) {
// We've got a surviving non-prime.
// Mark all its multiples as non-prime.
for (let i = p * p; i <= n; i += p) {
delete primes[i];
}
}
}
// Surviving numbers are primes.
return Object.keys(primes).map(x => Number(x));
}
Once we’ve got that, then the sum-of-primes method is just an array sum:
function sumOfPrimes(n) {
return sieveOfEratosthenes(n).reduce((sum, x) => sum + Number(x), 0);
}