DEV Community

Viren B
Viren B

Posted on • Originally published at virenb.cc

Solving "Sum All Primes" / freeCodeCamp Algorithm Challenges

Post can also be found on https://virenb.cc/fcc-029-sum-all-primes

Sum All Primes

Let's solve freeCodeCamp's intermediate algorithm scripting challenge, 'Sum All Primes'.

Starter Code

function sumPrimes(num) {
  return num;
}

sumPrimes(10);

Instructions

A prime number is a whole number greater than 1 with exactly two divisors: 1 and itself. For example, 2 is a prime number because it is only divisible by 1 and 2. In contrast, 4 is not prime since it is divisible by 1, 2 and 4.

Rewrite sumPrimes so it returns the sum of all prime numbers that are less than or equal to num.

Test Cases

  • sumPrimes(10) should return a number.
  • sumPrimes(10) should return 17.
  • sumPrimes(977) should return 73156.

Our Approach

The instructions for this challenge are short and to the point.

  • Our one input is num, an integer.

  • We must return an integer.

  • We need to do two things. Identify all the prime numbers within num and then add them up.

So, before we start, if we re-read the instructions, it provides us with a definition of what a prime number is.

A prime number is a whole number greater than 1 with exactly two divisors: 1 and itself. For example, 2 is a prime number because it is only divisible by 1 and 2. In contrast, 4 is not prime since it is divisible by 1, 2 and 4.

Some examples of prime numbers: 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

So, hopefully that gives a better idea on what a prime number is and how to find out if a number is prime.

For this challenge, I think it would be best if we broke it up into two parts. One part is to write code on figuring out if a number is prime. The second part would be to calculate the sum of all the prime numbers (within num).

Let's start with prime numbers. From the above description, a prime number is divisible only by itself and 1. While making our prime number checker function, we can start with an if statement. If the argument is less than or equal to one, we can return false as it will not be a prime number. Even though the test cases do not give us a number so small, I included it anyway.

function isPrime(n) {
  if (n <= 1) return false;
}

The modulo operator will be very useful as we can check the divisibility of each number. I'll opt to use a for loop to check how many divisors n will have.

We can start the checking with 2.

for (let i = 2; i <= (n/2); i++) {}

So, if our number is 11 (a prime number), it would run 4 times.

Inside the for loop, we can write an if statement checking if n is divisible by i. If it returns a remainder of 0, we know it is not a prime number. We can return false. Here is the updated code.

function isPrime(n) {
  if (n <= 1) return false;
  for (let i = 2; i <= (n/2); i++) {
    if (n % i === 0) {
      return false
    }
  }
}

We would determine n is divisible by more than just 1 and itself, so it wouldn't be a prime number. We would return false and exit the loop. If it is not divisble by i at all, we know it is a prime number. We can return a true.

function isPrime(n) {
  if (n <= 1) return false;
  for (let i = 2; i <= (n/2); i++) {
    if (n % i === 0) {
      return false
    }
  }
  return true;
}

Let us try it out with a small number, 5:

isPrime(5);

function isPrime(n) {
  if (n <= 1) return false;
  for (let i = 2; i <= (n/2); i++) {
    if (n % i === 0) {
      return false
    }
  }
  return true;
}

// n = 5
// First line, is not true, so keep it running
// First for loop, 5 % 2 !== 0 

// There is no second loop, because i = 3 and it is bigger than 5/2
// 5 is a prime number

Let's try with 9 now:

isPrime(9);

function isPrime(n) {
  if (n <= 1) return false;
  for (let i = 2; i <= (n/2); i++) {
    if (n % i === 0) {
      return false
    }
  }
  return true;
}

// n = 9
// First line, is not true, so keep it running
// First for loop, 9 % 2 !== 0 

// Second loop, i = 3, 3 <= (9/2) still true
// 9 % 3 === 0 is true so we return false
// 9 is not prime as it is divisible by 1, 3, 9

Hopefully that helped grasp the prime number part of the challenge. Now that we have a helper function to determine prime numbers, we can see how to sum the prime numbers of num.

So we'll be using another for loop. Before we start looping, I will declare a variable, sum, and set it to 0. This will be the number we return.

let sum = 0;
function sumPrimes(num) {
  let sum = 0;
    // For loop 
  return sum;
}

So we want to go through every number smaller than num, and check if its a prime number. If it is, we will add it into our new variable, sum.

for (let j = 1; j <= num; j++) {
  if (isPrime(j)) {
    sum += j;
  }
}

Having this helper function makes the this function a lot more cleaner. It evaluates each number, and will add it into the sum if it is prime.

function sumPrimes(num) {
  let sum = 0;
  for (let j = 1; j <= num; j++) {
    if (isPrime(j)) {
      sum += j;
    }
  }
  return sum;
}

Our Solution

function sumPrimes(num) {
  let sum = 0;
  for (let j = 1; j <= num; j++) {
    if (isPrime(j)) {
      sum += j;
    }
  }
  return sum;
}

function isPrime(n) {
  if (n <= 1) return false;
  for (let i = 2; i <= (n/2); i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

Links & Resources

'Sum All Primes' Challenge on fCC

freeCodeCamp

Donate to FCC!

Solution on my GitHub

Thank you for reading!

Top comments (1)

Collapse
 
ttatsf profile image
tatsuo fukuchi • Edited

You can do it faster to use Math.sqrt(n) instead of n/2. :

function isPrime(n) {
  if (n <= 1) return false;
  for (let i = 2; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      return false;
    }
  }
  return true;
}

If you need more speed / efficiency, you can use the memoizer function to get primes:

const memoizer = inits => rule =>{
  const memo = [...inits]
  const a = n => {
    if(n >= memo.length) {
      for(let i = memo.length; i <= n; i++) {
        memo[i] = rule( a )( i )
      }
    }
    return memo[n]  
  }
  return a
}

const nomineeG = value => function*(){
  let m = Math.ceil(value / 6) * 6
  if ( value === m - 5 ) yield m - 1
  while (true) {
    yield  m + 1
    yield  m + 5
    m = m + 6
  }
}()

const isAllIndivisible = a => value => {
  const end = Math.sqrt(value) 
  for (let i = 0; a(i) <= end; i++){
    if (value % a(i) === 0) return false
  }
  return true
}

const primeInits = [2, 3, 5]

const primeRule = a => n => {
  for (const nominee of nomineeG( a(n - 1) ) ) {
    if ( isAllIndivisible(a)(nominee) ) return nominee
  }
}

const primeAt = memoizer( primeInits )( primeRule )

const primeG = function*(){
  let i = 0
  while (true) {
    yield primeAt(i)
    i = i + 1
  }
}

const sumPrimes = n =>{
  let sum = 0
  for ( const v of primeG() ) {
    if ( v > n ) return sum
    sum = sum + v
  }
}