Sum All Primes: doesn't works with 977

Hello,
Sum All Primes

So bad, my code doesn’t works with 977, why ?

function sumPrimes(num) {
  let maxMultiple = Math.floor(Math.sqrt(num));
  console.log(maxMultiple)

    let multiples = [];
  for (let m = 2; m <= maxMultiple; m++) {
    multiples.push(m)
  }
  //console.log(multiples)

    let numbers = [];
  for (let n = 2; n <= num; n++) {
    numbers.push(n);
  }
  //console.log(numbers)
  for (let i = 0; i < multiples.length; i++) {
   		let multi = multiples[i];
    for (let j = numbers.indexOf(Math.pow(multi, 2)) ; j < numbers.length; j += multi) {
        numbers.splice(j, 1, 'false')
    }
  }
console.log(numbers)
console.log(numbers.filter(item => Number.isInteger(item)).reduce((a, b) => a + b, 0))
return numbers.filter(item => Number.isInteger(item)).reduce((a, b) => a + b, 0);
}


sumPrimes(977);

This is an interesting almost sieve approach. With some tweaks it could be really fast.

Is your approach correctly finding 977 as prime?

numbers.length is egal to 976 so it’s ok normaly :thinking:

But is 977 actually marked as prime?

I don’t understand:
977 is max numbers to check and the result must be 73156.
There are 977 elements in my array “numbers”, but the result is 20867.

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

I would start by looking at your numbers array and seeing if the numbers left in there are actually prime…

You are severely undershoting, so you have to be marking some primes as not prime.

If I was to guess, you have some subtle indexing flaw. This is easier with a proper prime number sieve.

This appears to be the offending line. You don’t need to use indexOf anyway, there is a arithmetic formula for index based on the number you want.

It’s weird because when I test with num = 10, it return [ 2, 3, 5, 7 ].
And with num = 120, 5 et 7 disapear.

Right… Because something is wrong with the use of indexOf. It is returning a -1 when it shouldn’t. Something with the slowness of the code I think.

So it’s not due to my code ?
I want to say , the logic of the code ?

Oh! It is because you have previously sliced out some of these values. 6^2 = 36 is a multiple of 4, for example. Mutation of an array as you iterate over it has to be done very carefully.

Direct indexing is faster than searching with indexOf anyways.

A true sieve would avoid this problem.

I know where is the problem.
j += item , this can’t work

No, that is perfectly fine. That is the correct way to increment j.

You cannot use indexOf. See my explanation above; you can’t get the index of a value you replaced with false. (Also, why splice instead of just changing the value? Faster/easier just to reassign) By replacing indexOf, I got your code to pass.

Part of what a traditional sieve does is avoid this problem by only marking multiples of primes as false. All multiples of a composite number are already marked once you get to that value.

Also, why not false instead of 'false'? The filter and reduce is easier with the actual boolean.

Yess! It’s better after a break.

function sumPrimes(num) {
  let maxMultiple = Math.floor(Math.sqrt(num));
    let multiples = [];
  for (let m = 2; m <= maxMultiple; m++) {
    multiples.push(m)
  }
    let numbers = [];
  for (let n = 2; n <= num; n++) {
    numbers.push(n);
  }
  for (let i = 0; i < multiples.length; i++) {
   		let multi = multiples[i];
    for (let j = Math.pow(multi, 2) ; j <= num; j += multi) {
      let indexOfNumber = numbers.indexOf(j);
      if (indexOfNumber > 0) {
        numbers.splice(indexOfNumber, 1, false)
      } 
    }
  }
//console.log(numbers)
console.log(numbers.filter(item => Number.isInteger(item)).reduce((a, b) => a + b, 0))
return numbers.filter(item => Number.isInteger(item)).reduce((a, b) => a + b, 0);
}

sumPrimes(977);

I added :
if (indexOfNumber > 0) { .

This was wrong:let j = numbers.indexOf(Math.pow(multi, 2)) ; j < numbers.length; j += multi)``Preformatted text
because “j” was an index instead of a value as I wanted. But as the code worked with num = 10, I didn’t notice it.
I’m happy to have gone through with my way.

Before going to see the FCC solutions, if you want that I try to do something in my code in order to improve it, I will do my best, if not thanks again for your time.

Nice work! Note that you could have just replaced j = numbers.indexOf() with a small formula without changing anything else.

The biggest thing that you can do to drastically speed up your solution is to remove unnecessary steps. Do you need the multiples array? Why use splice instead of assignment? Why use indexOf when there is a formula to get the index from the value (2 is at 0, 3 is at…)? If the number is already marked false, should you need to mark it’s multiples? Could you do this all with a single boolean array? You can sum as you go to avoid extra passes through the data.

Thank you, I will try to do better taking into account your comments tomorrow. :wink:

It’s definitely a classic problem for efficient, fast code for a reason! It’s a good problem to practice on.

Hello,
I think I answered your requests exepted for the last one:

function sumPrimes(num) {
  let maxMultiple = Math.floor(Math.sqrt(num));
  let numbers = [];
  for (let n = 2; n <= num; n++) {
    numbers.push(n);
  }
  for (let i = 2; i <= maxMultiple; i++) {
    for (let j = Math.pow(i, 2) ; j <= num; j += i) {  
     if ( j !== false) {
       numbers[j - 2] = false;
      }  
    } 
  }
//console.log(numbers)
console.log(numbers.filter(item => Number.isInteger(item)).reduce((a, b) => a + b, 0))
return numbers.filter(item => Number.isInteger(item)).reduce((a, b) => a + b, 0);
}

sumPrimes(977);

Have you one more hint ?

You’re pretty close. At this point, personally I think it would be totally fair to look at the third solution or the advanced solution in this thread
https://forum.freecodecamp.org/t/javascript-performance-measurement-variability/394059

The big changes I would make are setting

numbers = Array(num).full(true);

(array allocation with a push is slow)

Initializing a sum = 0 outside of the first loop and replacing the reduce with a sum over the rest of the values
(you are already iterating from 2 to sqrt(num) so you might as well sum up as you go)

Put the j loop inside of the if statement for numbers[j] === true
(if j is composite, then all multiples have already been marked. All multiples of 6, for example, are also multiples of 2 and 3)