freeCodeCamp Algorithm Challenge Guide: Sum All Primes

freeCodeCamp Algorithm Challenge Guide: Sum All Primes
0

#1

:triangular_flag_on_post: Remember to use Read-Search-Ask if you get stuck. Try to pair program :busts_in_silhouette: and write your own code :pencil:

:checkered_flag: Problem Explanation:

The explanation for this problem is very simple. You will generate a list of prime numbers up to the number you are given as a parameter. Then you need to add them all up and return that value. The tricky part is on generating the list of prime numbers. I suggest you find a code or a good math algorithm that you can turn into code.

Relevant Links

:speech_balloon: Hint: 1

Generate a list of all the numbers up to and including the one you got as a parameter. This will be needed to determine which numbers are prime or not.

try to solve the problem now

:speech_balloon: Hint: 2

Check this link if you prefer to find a solution for finding primes, or try learning and implementing your own Sieve of Eratosthenes

try to solve the problem now

:speech_balloon: Hint: 3

This problem is hard if you have to create your own code to check for primes, so don’t feel bad if you had to use someone’s code for that bit. Either way, you are most likely using array, so once you generate an array of primes, then just add them all up and return the number you get.

try to solve the problem now

Spoiler Alert!

687474703a2f2f7777772e796f75726472756d2e636f6d2f796f75726472756d2f696d616765732f323030372f31302f31302f7265645f7761726e696e675f7369676e5f322e676966.gif

Solution ahead!

:beginner: Basic Code Solution:

function sumPrimes(num) {
  var res = 0;

  // Function to get the primes up to max in an array
  function getPrimes(max) {
    var sieve = [];
    var i;
    var j;
    var primes = [];
    for (i = 2; i <= max; ++i) {
      if (!sieve[i]) {
        // i has not been marked -- it is prime
        primes.push(i);
        for (j = i << 1; j <= max; j += i) {
          sieve[j] = true;
        }
      }
    }

    return primes;
  }

  // Add the primes
  var primes = getPrimes(num);
  for (var p = 0; p < primes.length; p++) {
    res += primes[p];
  }

  return res;
}

// test here
sumPrimes(10);

:rocket: Run Code

Code Explanation:

  • Create a function that generates the numbers from 1 to num and check if they are prime along the way.
  • Declare the variables that will be needed.
  • Start with 2, if it has not been marked and added to the sieve array then it is a prime and we add it to the prime array.
  • Add the others to the sieve array.
  • Return the primes
  • Loop through the returned array and add all the elements to then return the final value.

Relevant Links

:sunflower: Intermediate Code Solution:

function sumPrimes(num) {
  // function to check if the number presented is prime
  function isPrime(number){
      for (i = 2; i <= number; i++){
          if(number % i === 0 && number!= i){
          // return true if it is divisible by any number that is not itself.
             return false;
          }
       }
       // if it passes the for loops conditions it is a prime
      return true;
  }
  // 1 is not a prime, so return nothing, also stops the recursive calls.
  if (num === 1){
    return 0;
  }
  // Check if your number is not prime
  if(isPrime(num) === false){
  // for non primes check the next number down from your maximum number, do not add anything to your answer
    return sumPrimes(num - 1);
  }

  // Check if your number is prime
  if(isPrime(num) === true){
  // for primes add that number to the next number in the sequence through a recursive call to our sumPrimes function.
    return num + sumPrimes(num - 1);
  }
}
// test here
sumPrimes(10);

:rocket: Run Code

Code Explanation:

  • The function isPrime checks if a particular number is prime or not.
  • If num is 1, return 0 since 1 is not a prime number.
  • If num is not prime, check next number down from maximum number.
  • If num is prime, add it to next number in the sequence through recursion to sumPrimes function.

Relevant Links

:rotating_light: Advanced Code Solution:

function sumPrimes(num) {
  // step 1	
  let arr = Array.from({length: num+1}, (v, k) => k).slice(2); 
  // step 2
  let onlyPrimes = arr.filter( (n) => { 
    let m = n-1;
    while (m > 1 && m >= Math.sqrt(n)) { 
      if ((n % m) === 0) 
        return false;
        m--;
    }
      return true;
  });
  // step 3
  return onlyPrimes.reduce((a,b) => a+b); 
}
// test here
sumPrimes(977);

:rocket: Run Code

Code Explanation:

  • Step 1: Use Array.from() to generate a sequence of numbers up to and including num. Combine with .slice() to slice off first two indices [0, 1] since all prime numbers must be greater than 1.
  • Step 2: Filter all numbers off of arr that are not prime by subjecting each element to the “trial division test” which “consists of dividing n by each integer m that is greater than 1 and less than or equal to the square root of n”. This test returns false if any number less than the element being operated on (m) produces no remainder when said element (n) is divided by it. See link below for more on this.
  • Step 3: Return the sum of all remaining elements of arr using .reduce().

Relevant Links

:clipboard: NOTES FOR CONTRIBUTIONS:

  • :warning: DO NOT add solutions that are similar to any existing solutions. If you think it is similar but better, then try to merge (or replace) the existing similar solution.
  • Add an explanation of your solution.
  • Categorize the solution in one of the following categories — Basic, Intermediate and Advanced. :traffic_light:

See :point_right: Wiki Challenge Solution Template for reference.


Doubts about a solution : Sum All Primes SPOILER
Question Algorithm Challenge Guide "Sum All Primes" Solution
#4

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


#5

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


#6

@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.


#8

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.

`


#11

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.


#12

Oh! @P1xt thank you so much!


#13

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


#14

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…


#15

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


#17

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


#18

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

#19
var m=Math.sqrt(n);
m=Math.floor(m);
while(m>1){
  if((n%m)===0) return false;
  m--;
}

#20

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

#21

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


#22

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”…


#23

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.


#24

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

#25

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

#26

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