Why is my algorithm failing at this number?

Question

I am trying to write an algorithm to calculate the sum of prime numbers less than or equal to a given number argument. Here is my code:

function sumPrimes(num) {
// populates the array with numbers uptp the given num
  let prime = [], i = 2;
  while (prime.indexOf(num) < 0){
    prime.push(i)
    i++;
  }
// filters the array leaving only the prime numbers and sums all prime numbers
  let result = prime
  .filter(function (a){
    if(a === 2 ||a === 3 || a === 5 || a === 7){
      return a
    } else {
      return a % 2 > 0 && a % 3 > 0 && a % 5 > 0 && a % 7 > 0
  }}).reduce((a,b) => a+b)
  
  console.log(result)
  return result
}
sumPrimes(977); //outputs 108789 instead of 73156

My filter function check if a given number divisible simultaneously by 2, 3, 5, 7 returns a remainder greater than zero if so such number is a prime number. However, when the supplied argument is 977, it falls apart and outputs the wrong sum. Can anyone figure out what is going on here?

Just because a number cannot be divided by 2, 3,5, and 7 does not mean it is prime. You need to use a different logic to check it, like this one: https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript — Terry, Jan 05 '21 at 23:09
I would appreciate suggestions, not just criticism as this was my first time attempting something like this — Frank Imade, Jan 05 '21 at 23:11
Your question was _"Can anyone figure out what is going on here?"_ The comment _"11^2 = 121 is neither prime nor divisible by 2, 3, 5, or 7."_ is a pretty concrete answer to your question. I can't see any criticism. — Thomas Sablik, Jan 05 '21 at 23:19

score 0 · Accepted Answer · answered Jan 05 '21 at 23:15

As per my comment: your check for prime is faulty. Just because a number cannot be divided by 2, 3, 5 or 7 does not mean it is prime. You can simply recycle the prime checking logic from this answer: Number prime test in JavaScript, and optimize your loop so that you only perform iteration once.

You start a for loop from 2, the smallest prime, increment it until it reaches your target number. In the for loop, check the number if it is prime: if it, add it to the sum.

The advantage of this approach is that:

You don't store an arbitrary large array of prime numbers in the prime array, which is eventually reduced by summing it up. Of course, this is under the assumption that you don't need the primes for anything else.
You don't need to perform several iterations, compared to your old code, where you perform repeated iterations in: (1) the while loop to generate all numbers between 2 and your target number, (2) the filter check for prime, and (3) the reduce method

// Adapted from: https://stackoverflow.com/questions/40200089/number-prime-test-in-javascript
function isPrime(num) {
  for (let i = 2, s = Math.sqrt(num); i <= s; i++)
    if (num % i === 0) return false;
  return num > 1;
}

function sumPrimes(num) {
  let sum = 0;
  
  for (let n = 2; n <= num; n++) {
    if (isPrime(n)) {
      sum += n;
    }
  }

  console.log(sum);
  return sum;
}
sumPrimes(977); // Outputs 73156 as expected

Thank you Terry, I don't understand why we check the sqrt of num here: s = Math.sqrt(num); i <= s; Mind shedding light on that please? — Frank Imade, Jan 05 '21 at 23:22
@FrankImade You don't need to check all the way to the actual number, because a prime number is defined by it being not multiple of an integer. The largest possible multiple is achieved by squaring a number, so you only need to check up to square root. Refer to original answer for a more in-depth explanation. — Terry, Jan 05 '21 at 23:24

score 0 · Answer 2 · answered Jan 05 '21 at 23:20

To check whether a number is prime it should not be divisible by any other prime. So while your logic is kind of correct, you need to expand your array of primes constantly. This could be achieves like this:

const primeArray = (n) => {
    var p = [2];
    if (n<2) return [];
    if (n===2) return [2];
    for (let i=3;i<=n;i+=2) if (p.every(x=>i%x)) p.push(i);
    return p;
  }

We start with the first prime and then we will check every second number starting from 3, as all even numbers are divisible by 2. While iterating through i+2, we simply check whether i is divisible by any already identified primes. If this is not the case (i%x), we expand the array of primes by i.

Carsten Massmann · Answer 3 · 2021-01-06T10:51:39.503

Here is another scalable minimalist and performance optimized version of the Erastostenes sieve with a cap for testing only up to the square root of the current number:

function primeArr(n){
  for (var primes=[],i=1,j=0,cap=2; ++i<=n;){
    if (i>2 && i==cap) cap=primes[j]*primes[j++];
    if (primes.slice(0,j-1).every(p=>i%p)) primes.push(i)
  }
  return primes;
}

let pa=primeArr(977);
console.log("sum:", pa.reduce((a,c)=>a+=c));
console.log("all primes:", pa.join(" "));

score 0 · Answer 4 · answered Sep 20 '22 at 00:46

0

Complete and fast solution via prime-lib:

import {generatePrimes, stopOnValue} from 'prime-lib';

const i = stopOnValue(generatePrimes(), 977);

let sum = 0;
for (let a of i) {
    sum += a;
}

console.log(sum); //=> 73156

answered Sep 20 '22 at 00:46

vitaly-t

24,279
15
116
138

Why is my algorithm failing at this number?

4 Answers4