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