https://algodaily.com/challenges/sumallprimes
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 notprime, you
start at the square of it (p * p ) and then iterate from there in increments of
p , marking all those numbers as notprime. In other words, you start from
p * p and mark all multiples of p as notprime.
Finally, rather than “marking as notprime”, 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 nonprime.
// Mark all its multiples as nonprime.
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 sumofprimes method is just an array sum:
function sumOfPrimes(n) {
return sieveOfEratosthenes(n).reduce((sum, x) => sum + Number(x), 0);
}
View post:
AlgoDaily 18: Sum All Primes
