Adding up all the primes up to a certain number

Question

I am supposed to write an algorithm that returns the sum of all the primes up to a certain number(argument), including the argument itself. This code seems to be working just fine(I tested it on smaller numbers),however there must be a bug because when I pass 977 as an argument, the programs returns 108789, which is supposedly not correct. According to freecodecamp.org, it should return 73156. I have already checked the array before adding the values but I can't see the problem here.

function sumPrimes(num) {
  function isPrime(n){
   return ((n/2 === 1 || n/3 === 1 || n/5 === 1 || n/7 === 1)?true: 
     (n%2===0 || n%3 === 0 || n%5 ===0 || n%7 === 0)? 
     false:true);
  };

  let result = [];
  let final;

  for(let i = 2; i <= num; i++){
    if(isPrime(i)){
      result.push(i);
    }
  }

  final = result.reduce((x,y) => x + y);

  console.log(final); // returns 108789

}

sumPrimes(977);

You better check your final array. it includes `121` which can be divided by 1, 11, 121. — Chase Choi, Jun 14 '19 at 04:22

Anjana · Accepted Answer · 2019-06-14T05:15:13.440

3

Your isPrime() method is incorrect. You can do some thing like below instead.

Edit: Complexity of the algorithm is decreased from O(n) to O(sqrt(n)) as pointed out by @Amadan

function sumPrimes(num) {

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

      let result = [];
      let final;

      for(let i = 2; i <= num; i++){
        if(isPrime(i)){
          result.push(i);
        }
      }

      final = result.reduce((x,y) => x + y); 
      console.log(final); // returns 73156
    }

edited Jun 14 '19 at 05:15

answered Jun 14 '19 at 04:35

Anjana

903
1
5
13

Many thanks to you, this is simple and comprehensible. – Peter Utekal Jun 14 '19 at 04:38
Why would you loop from `0` to `n`, then exclude `n` and `1`? (Leaving alone the weirdness of `n%0`, which luckily gets you `NaN` in JavaScript rather than breaking your code) Why not just loop from `2` to `n - 1`? Or even better, from `2` to `Math.sqrt(n)`, which is mathematically sufficient (as mentioned in my answer)? – Amadan Jun 14 '19 at 04:38
@Amadan completely agree..i'll edit right away. That is way better than this. – Anjana Jun 14 '19 at 04:39
yup...Missed that. Couldn't even see it. Thanks again. – Anjana Jun 14 '19 at 05:16

Amadan · Answer 2 · 2019-06-14T04:27:03.750

Your isPrime is completely wrong. First of all, you only check divisibility by first four primes; you should check divisibility by all primes up to square root of the number you're testing to be sure. (You can test with non-prime numbers too if you don't want to bother sorting primes from non-primes at this point.) Secondly, whether a remainder is 1 or not makes no difference - it's only between 0 and not 0 that is important.

The algorithms for primality testing are very well-known and described all over the Web; for start, take a look at Wikipedia on prime numbers for overview, and here for the specific algorithm I assume you were going for, though for your specific use case (sum of all primes less than N), the Sieve of Eratosthenes should be much better.

Thank you, I did not realise that, this prime checking has been such a pain in the ass for me but hopefully I can get my head around it soon. — Peter Utekal, Jun 14 '19 at 04:35

score 0 · Answer 3 · answered Jun 14 '19 at 04:21

0

Your isPrime() function is incorrect. If you want to handle anything beyond trivially small primes you cannot simply hardcode the primes to check. For instance isPrime(143) will return true, but 143 = 11*13 so is not prime.

answered Jun 14 '19 at 04:21

weirdev

1,388
8
20

score 0 · Answer 4 · answered Jun 14 '19 at 04:24

0

Your prime function doesn't work properly, you might want to read this post about building one. The rest of your function, however, seems to be acting as expected.

answered Jun 14 '19 at 04:24

Sebastien Dufresne

755
4
17

score 0 · Answer 5 · answered Jun 14 '19 at 04:53

The method you are using is wrong as it only checks for a certain number of values which would be problematic for large numbers.

As mentioned in one of the answers above, looping through all the numbers till the square root of that number is also a valid method however there's an even faster and more efficient method named Sieve of Eratosthenes.

This method works on removing results that we already know as false and not computing on them.

You may read about it more over here - Sieve of Eratosthenes

Adding up all the primes up to a certain number

5 Answers5