freeCodeCamp Challenge Guide: Problem 10: Summation of primes

Problem 10: Summation of primes


Problem Explanation

  • In this challenge we need to find sum of all prime numbers up to n.
  • Example:
    • If n = 10 then prime numbers before it are 2, 3, 5, 7 and their sum is 17.

Solutions

Solution 1 - Divisibility checking (Click to Show/Hide)
function primeSummation(num) {
  // Helper function to check primality
  function isPrime(num) {
    for (let i = 2; i <= Math.sqrt(num); i++) {
      if (num % i == 0)
        return false;
    }
    return true;
  }

  // Check all numbers for primality
  let sum = 0;
  for (let i = 2; i < num; i++) {
    if (isPrime(i))
      sum += i;
  }
  return sum;
}

Code Explanation
We loop over all values in our range, adding them to the sum if they are prime.
Our primality checking function returns false if the target number is divisible by any number in between 2 and the square root of the target number. We only need to check up to the square root because the square root of a number is the largest possible unique divisor.

Solution 2 - Prime number sieve (Click to Show/Hide)
function primeSummation(num) {
  // Prime number sieve
  let isPrime = Array(num).fill(true);
  // 0 and 1 are not prime
  isPrime[0] = false;
  isPrime[1] = false;
  for (let i = 2; i <= Math.sqrt(num - 1); i++) {
    if (isPrime[i]) {
      // i has not been marked false -- it is prime
      for (let j = i * i; j < num; j += i)
        isPrime[j] = false;
    }
  }

  // Sum all values still marked prime
  return isPrime.reduce(
    (sum, prime, index) => prime ? sum + index : sum, 0
  );
}

Code Explanation
This solution is based on the Sieve of Eratosethenes.
We create a boolean array for the primality of each number in our range. All numbers except 0 and 1 are assumed to be prime.
Then, we start with 2 and proceed to num, marking every multiple of a prime number as false, or ‘not prime’.
Finally, we reduce our sieve array, returning the sum of all indices still marked as true or ‘prime’.
Note: many optimizations can be made to improve the efficiency of this sieve, but they have been omitted for the sake of simplicity and readability.

2 Likes

I think you should revert the changes you made to the Solutions section of this guide post. We always want the user to be able to copy/paste the solution and it pass the tests in the challenge.