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