freeCodeCamp Challenge Guide: Sum All Primes

Sum All Primes


Problem Explanation

For this problem will find all prime numbers up to the number you are given as a parameter and return their sum. It is a good idea to research algorithms for finding prime numbers.

Relevant Links


Hints

Hint 1

You can use the definition of prime numbers or try learning and implementing your own Sieve of Eratosthenes. Check this link to see a StackOverflow discussion on various ways of finding prime numbers.

Hint 2

This problem can be hard if you create your own code to check for primes, so don’t feel bad if you use someone’s algorithm for that part. Research is an important part of coding!


Solutions

Solution 1 - Divisibility checking (Click to Show/Hide)
function sumPrimes(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 - List of prime numbers (Click to Show/Hide)
function sumPrimes(num) {
  // Check all numbers for primality
  let primes = [];
  for (let i = 2; i <= num; i++) {
    if (primes.every((prime) => i % prime !== 0))
      primes.push(i);
  }
  return primes.reduce((sum, prime) => sum + prime, 0);
}

Code Explanation
This solution is very similar to Solution 1.
In this solution we retain a list of all primes found so far and check if any of these numbers divide into each number in our range.
Note that this solution is actually less efficient than Solution 1 for very large values of n. Frequently growing the size of an array in JavaScript can be inefficient and slow.

Solution 3 - Prime number sieve (Click to Show/Hide)
function sumPrimes(num) {
  // Prime number sieve
  let isPrime = Array(num + 1).fill(true);
  // 0 and 1 are not prime
  isPrime[0] = false;
  isPrime[1] = false;
  for (let i = 2; i <= Math.sqrt(num); 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.

26 Likes

Hi there! I’d like to add Advanced Code Solution for this algorithm. How can I do this?

5 Likes

is this a challenge for the community to come with the most efficient code?

2 Likes

@amazigh1989 these are different solutions of varying levels for the challenge in free code camp, You should not even be looking at the code if you haven’t come up with your own solution. We provide hints and explanations before the solutions.

@oshliaer you can edit the article and please do follow the same patterm when it comes to formatting as the others. Check other challenges with advanced solutions so you can see how it must look like.

This is my basic solution the problem. please I want from you to give me feedback about it.

What I want to tell by looking for an efficient algorithm is looking for a scientifc paper that describe an efficient algorithm., not its actual implementation in a specific programing language. Our job then is implementing it efficiently in JS.

`

8 Likes

thank you @P1xt. I will implement the algorithm you suggested. and then I will compare it to your implementation. I have not yet seen you solution just for this reason :slight_smile:. For my code I know exactly how it works. it’s not my first time coding. I have background in Matlab for numerical methods and signal processing. I care a lot to compare my code with code of others in oder to learn new technics. Thank again a lot for your feedback.

Oh! @P1xt thank you so much!

i am not sure making code like that I improved its performance. But it definetly make less computation.
function sumPrimes(num) {

var arr = new Array(num+1);
var toplam=0;
var sayac;

for(var k =1;k<num+1;k+=2)
arr[k]=true;

for(var z = 3;z<=Math.sqrt(num);z+=2) {
sayac = 2*z;
if(arr[z+sayac])
for(var i=z+sayac;i<=num;i+=sayac)
arr[i] = false;
}

for(var y=3;y<=num;y++)
if(arr[y])
toplam += y;

return toplam+2;
}

1 Like

I had fun with this one re-reading about the differences in operation speed and memory usage of different prime-generating algos. I decided not to go crazy and stick to a Eratosthenes-ish solution: a version of an Euler sieve. I’d be curious if anyone could think of more optimizations to it than I have, without resorting to an entirely different approach.

function sumPrimes(num) {

  var max_sqrt = Math.sqrt(num); //max # needed to be checked as a divisor
  //initialize array of "2" followed by all the odd #s <= num
  var primes = [2];
  for (var j=1; j<num/2; j++)
    primes.push(j*2+1); 
  
  var i = 1;  //iterate over array removing divisors of the current item
  while(primes[i] <= max_sqrt) {
    var pofISq = Math.pow(primes[i], 2);
    primes = primes.filter((primeFilt));
    i++;
  }
  
  function primeFilt(el) {
    if (el < pofISq) return true; //don't need to check items less than the current item squared
    return (el % primes[i] != 0); //non-divisors stay
  }
  
  return primes.reduce((a,b) => a+b);

}

I find it interesting that a codepen based on p1xt’s comment above yields very different results for chrome and firefox. (results in console, open inspector to see) I get diff results running the pen in-place or edit too…

Why would using a bitwise operator be consider a basic solution? I never heard of it until now.

4 Likes

How about this solution?

function sumPrimes(num) {
  var x=2;
  var added=2;
  while (x<num) {
    x++;
    for (var i=2;i<x;i++){
      if (x%i===0){
        break;
      }
      else if (i===x-1) {
        added+=x;}
      }
   }
  return added;
}

sumPrimes(10);

16 Likes

Hey, I like your solution. It was a little bit tough to follow through in your mind at first, but my solution does pretty much the same only with a different syntax. Check it out:

function sumPrimes(num) {
  var numbers = [];
  
  //create an array of numbers up to and including num
  for (var i = 2; i <= num; i++) {
    numbers.push(i);
  }
  
  //filter all numbers in the 'numbers' array, that are not divisible by any number other than themselves without a remainder
  return numbers.filter(function(item, index, array) {
    for (var j = 0; j < index; j++) {
      if (item % array[j] === 0)
        return false;
    }
    return true;
    
  //sum up all numbers in the filtered array (=primes)
  }).reduce(function(a, b) {
    return a + b;
  });
}
8 Likes
var m=Math.sqrt(n);
m=Math.floor(m);
while(m>1){
  if((n%m)===0) return false;
  m--;
}
2 Likes

Offering an additional solution. It’s very inefficient, but it is pretty simple.

I rely on the fact that a prime has only two numbers that can divide it with no remainder, one and itself.

If you exclude 1, it can only be divided by one number.

function sumPrimes(num) {
 
  var prime_sum = 0;
  
for (i = 2; i <= num; i++) {
  var c = 0;
  for (n = 2; n <= i; n++) {
    if (i%n === 0) {
      c++;
    }
  }
  
  if (c == 1) {
    prime_sum += i;
  }  
}
  
return prime_sum;

}

sumPrimes(977);
1 Like

Hi, can someone take a look at this code and tell me whats wrong with it?
I used an array to list the primes between 0 and 1000, as i didnt know how to make a function to generate them. My code gets the answers right except for the last one (997).

//
function sumPrimes(num) {
var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997];
var arr=[];
var result =0;

for (i = 0; i <= (Math.sqrt(num)); i++){
arr.push(primes[i]);
}
for (i=0;i<arr.length;i++){
result += arr[i];}

return result;
}

sumPrimes(10);
//

You’re only testing for primes up until the square-root of the given number which does not allow you to successfully test numbers higher than the square-root of “num” (and then to add them to your “result” variable).

To successfully complete the challenge you must:
“Sum all the prime numbers up to and including the provided number.”

As a little suggestion:
Maybe you could consider counting back from the given value (“num”) adding every prime to “result”…

1 Like

I’ll have to read the solutions posted here so I can optimize, but this is what I came up with:


function sumPrimes(num) {
  var pArr = [];
  function primeCheck(k) {return i % k !==0;}
  
  for(var i of Array.from(Array(num + 1).keys()).slice(2)) {
    if(i < 4) {pArr.push(i);}
    else {
      let pChk = Array.from(Array(i).keys()).slice(2);
      if(pChk.every(primeCheck)) {pArr.push(i);}
    }
  }
  num = pArr.reduce(function(a, b) {return a + b;}, 0);
  return num;
}

EDIT: yeah… not a good solution. Tested with some larger numbers and wow, talk about a crapper on performance.

This is my solution :slight_smile:

function sumPrimes(num) {
var primesArr=[],sumOfPrimes;

  for(var i=2;i<=num;i++){
    if(isPrime(i)){
        primesArr.push(i);
    }
  }
  
  sumOfPrimes = primesArr.reduce(function(acc,val){
    return acc+val;
  });
  
  return sumOfPrimes;
}

function isPrime(number){
 var counter = 0;
  
  for(var i=1;i<=number;i++){
     if(number%i===0){
         counter++;
     }
  }
  
  
  if(counter==2){
    return true;
  }
  else return false;
  
}

My solution:

const isPrime = num => {
	for (let i = 2; i < num; i++) if (num % i === 0) return false;
	return num !== 1;
};

const primes = num => [...Array(num + 1).keys()].filter(isPrime);

const sumPrimes = num => primes(num).reduce((current, prev) => current + prev);

// TEST
sumPrimes(10); // => 17
sumPrimes(977); // => 73156
1 Like

Mine :slight_smile:

function sumPrimes(num) {
var prime = []; //an array to store primes

for(var i=2; i<=num; i++){   //loop all natural num from 2 up to "num"
var count = 0;             //var to count %===0 for each number   
for(var j=1; j<=i; j++){   //loop each number and check if it is 
   if(i%j===0){            //divisible by any number smaller or eqeual to
     count++;              //itself and increament count each time 
   }      
 }
if(count===2){          //prime number have only 2 divisors so count===2
  prime.push(i);        //push it to prime array         
  }
}

return prime.reduce(function(a,b){return a+b;}); //reduce to sum all the numbers in the prime array and return it.
}

sumPrimes(977);
1 Like