Intermediate Algorithm Scripting: Sum All Primes Error

JavaScript
1

So, I am doing the Sum All Primes Challenge, and my code on FCC passes the first 2 tests, but fails the final test, saying it should add to 73156. However, when I run my code on this website https://repl.it/repls/WrithingAwesomeMetrics, the output IS 73156. Why does it not pass on FCC?

My code is below (May give spoilers, don’t know how to blur it, so would be great if someone could do this for me):
function sumPrimes(num) {
var arr1 = [];

for (var i = 2; i<=num;i++){
arr1.push(i);
}

var arr2 = arr1;

for(var i=0; i<arr1.length; i++){
for(var j=0; j<arr2.length;j++){
if (arr1[i] !== arr2[j] && arr1[i]%arr2[j]===0){
delete arr1[i];
}

}
}
var Primes = arr1.filter(Boolean);

return Primes.reduce((a,b) => a + b);

}

sumPrimes(977);

2

Your code is too slow, the tests are timing out. You’re making a vast number of unnecessary calculations by brute forcing the algorithm (you’re testing every single value, most of which don’t need to be tested - ie you’ve either already tested them or they can’t possibly be primes [any even number that isn’t 2, for example])

Side issue, but I think you think that you’re making a copy here?

var arr2 = arr1;

That’s just the same array, you’re just saying arr2 is a reference to arr1, it isn’t a copy

3

Yeah, I wanted to make it the same. Ill try and cut some stuff out and see

4

What would you say is the best way to simplify this code to speed it up?

5

There are easier ways to generate a prime factor array.

let arr = [];
let n = 977;

if (n > 1) arr.push(2);

for (let i = 3; i<=n; i+=2) {
	if (arr.every(x => i%x !== 0)) arr.push(i);
}

I am sure you can improve it even further.
One suggestion would be to not create an array at all, just a variable that acts as a counter to which the next prime numbers are add to.
Using reduce on large arrays will slow down your program.

happy coding

6

What @EdMagal said - there isn’t any need to create an array because you’re just adding up the numbers that match.

You can also memoize the function. Initialise an object at the top of the function (eg memo = {}). On every iteration, check if the value you’re going to check has already been checked (if (value in memo)). If it has, you can ignore it. If it hasn’t, add the value to memo and do whatever with it (eg add it if it’s a prime) - memo[value] = null. That way, you only ever really make use of every discrete value once

8

@EdMagal:This is the best solution i have come across…Thank you

1 Like