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);
}

Tech mentioned