DEV Community

stuxnat
stuxnat

Posted on

JavaScript Algorithm: Sum of All Primes

This problem asks to return sum of all prime numbers that are less than or equal to a given number.

A prime number is a whole number greater than 1 with exactly two divisors: 1 and itself.

Here is how to solve that algorithm:

Step 1. Set up the algorithm, accounting for the number 2 (the lowest prime):

function sumprime(num){
    if (num < 2){
        return 0; 
    }
    return num;
}

sumprime(10); 
Enter fullscreen mode Exit fullscreen mode

Step 2. If num is greater than 2, we want to keep track of all the prime numbers up to and including the given parameter. We will need to use a for loop to check for composite numbers (the opposite of prime).

function sumprime(num){
    if (num < 2){
        return 0; 
    }

    const primes = [];
    for (let i = 2; i <= num; i++){
        let composite = false; 
        for (const p of primes){
            if (i % p === 0){
                composite = true; 
                break; 
            }
        }
        if (!composite){
           primes.push(i)
        }
    }
    console.log(primes)
    return num; 
}

sumprime(10); 
Enter fullscreen mode Exit fullscreen mode

Step 3. Sum up the numbers!

function sumprime(num) {
    if (num < 2) {
        return 0;
    }

    const primes = [];
    for (let i = 2; i <= num; i++) {
        let composite = false;
        for (const p of primes) {
            if (i % p === 0) {
                composite = true;
                break;
            }
        }
        if (!composite) {
            primes.push(i)
        }
    }
    let sum = 0;
    for (const p of primes) {
        sum += p;
    }
    return sum;
}

sumprime(10);
Enter fullscreen mode Exit fullscreen mode

Top comments (1)

Collapse
 
lexlohr profile image
Alex Lohr • Edited

This is a (pun intended) prime example of recursion allowing a more concise solution:


const sumPrime = (max, current = 2, divisor = 2, sum = 0) =>
  // reached end of recursion, return sum
  current > max
  ? sum
  // found prime, add to sum and run with next value
  : current % divisor === 0
  ? sumPrime(max, current + 1, 2, sum + current)
  // value is is not a prime, run with next value
  : divisor >= current / 2
  ? sumPrime(max, current + 1, 2, sum)
  // otherwise increase divisor
  : sumPrime(max, current, divisor + 1, sum);
Enter fullscreen mode Exit fullscreen mode

Your solution is valid, just the use of an array to sum up the primes is superfluous.