# Problem 10: Summation of primes : How can I optimize further?

Tell us what’s happening:
I asked this question earlier but didn’t get any help so hoping this time somebody can enlighten me!

I am able to get the right answers in my console but my solution is not passing in FCC. Not sure what else I can do to optimize my solution.

``````
function primeSummation(n) {
let primes = []
for (let i = 2; i < n; i++){
if (isPrime(i)){
primes.push(i)
}
}

return primes.reduce((a,b)=> a+=b)

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

primeSummation(2000000);
``````

User Agent is: `Mozilla/5.0 (Macintosh; Intel Mac OS X 10_11_6) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/71.0.3578.98 Safari/537.36`.

Generally, a good, efficient way to find a lot of primes is the Sieve of Eratosthenes, and ancient Greek algorithm. Look it up. Basically you know the highest prime you need, you start with 2 mark all of it’s multiples (up to the max) as “not prime”. Then you go to the next one not marked (3) and that is a prime. Mark all of its multiples. Then go the the next (5), etc. This is a fairly efficient algorithm to generate all of the primes up to a certain number. The problem with your solution is that you end up recalculating a lot of things that you shouldn’t need to, and those calculations involve the modulo, which is an inherently slow operation. Your approach is intuitive, and is the one that most people try first, but it is not the fastest. See if you can execute the Sieve of Eratosthenes. I think wikipedia has a gif of it working. I’ll give you a hint - you’re going to need an array.

1 Like

I would also add that the Sieve of Eratosthenes is an algorithm you should know how to do from memory. Prime numbers show up in a lot of algorithm challenges on interviews, and if you don’t know it, it looks bad.

once again I’m getting the right answers in the console but FCC won’t let me pass. Just wanted to double check to see it’s not me.

``````function primeSummation(num) {
const sieves = new Array(num).fill(true)

for (let i = 2; i < Math.sqrt(num); i++){
for (let j = i*i; j < num; j += i){
if (sieves[i]){
sieves[j] = false
}
}
}

return sieves.reduce((a,b,i)=>{
if (b && i > 1 ){
a += i
}
return a
}, 0)
}

primeSummation(2000000);``````

I haven’t actually tried to understand you code, but from a quick glance it looks like you’re missing a lot of semi colons. Try adding those.

`
function primeSummation(num) {
const sieves = new Array(num).fill(true);

for (let i = 2; i < Math.sqrt(num); i++){
for (let j = i*i; j < num; j += i){
if (sieves[i]){
sieves[j] = false;
}
}
}

return sieves.reduce((a,b,i)=>{
if (b && i > 1 ){
a += i ;
}
return a;
}, 0);
}

primeSummation(2000000);
`

semi-colons don’t affect how the code runs in JS

That’s because you’re a noob, professionals like me use JSLint before minifying the JS via Gulp, Grunt, or Webpack.

lol. i hope you’re just trolling…

i am def. a newb but how do semi-colons affect how the code executes in this particular problem?

Let’s not insult. There are a lot of good coders who don’t use semicolons. And it is not an issue in this case. (Technically it can matter sometimes, but not here.)

I’m trying to understand what you are doing. First of all, I will say that this is a good first attempt at a sieve.

Here:

``````const sieves = new Array(num).fill(true)
``````

If you are using the index to represent the number you are testing (essentially wasting slot 0, but OK) don’t you need to do `num+1`? If num is 10, this will only give you indexes up to 9.

I like that your i loop only goes up to `Math.sqrt(num)`, but rather than calculate that every time, why not save it in a variable in the line before?

I think your `if (sieves[i])` is in the wrong place. Shouldn’t it be outside the j loop? If `sieves[i]` is not prime, then there is no need to do the j loop because all the multiples of i have already been marked.

And:

``````for (let j = i*i; ...
``````

Should that be `i*i` there? Don’t you want to start at `i*2`?

And in your reduce, rather than check `i > 1` 2000000 times, why not just manually set those two indices as `false` before you begin - seems faster.

Never mind that first comment, I just reread the problem, they want everything up to, but not includeing num.

im gonna take some time to think about your notes but doesn’t my solution give the correct outputs?

Yes, but it’s very strict on the time controls. They want you to get an efficient solution. Trust me, that’s the kind of thing that can happen on a job interview. If it’s any consolation, I’m having a hard time getting it to pass.

A thought, what if instead of filling the array with `true`, what if you just left them `undefined`? It would be a little faster. Then the array would represent not primes, instead of primes.

Well, it’s time for bed. This is a hard one. The controls are a lot tighter on this one than they used to be. I’ll have to thing about this one.

Actually, I just looked at the github and it seems like there was a discussion a few months ago about the time controls being too difficult for this one and there was no working solution. I don’t know if it got fixed or if it did, if it’s made it to the site yet.

I think I’ve made mine about as efficient as I can and it still won’t pass. I wouldn’t worry about it. This site isn’t perfect and there are some things being improved. You’ve learned a lot from this. At the very least, hopefully you’ll remember how to make a sieve. I’ll keep thinking about this, but I don’t think I can make one that passes.

1 Like

really appreciate the help Kevin! definitely learned a lot from this problem…although unnecessarily frustrating!

Yeah. But you got a working solution! You solved it! I think the FCC test just needs some tweaking. But I would take a look at those optimizations I mentioned and understand why. And then move on. Good work.

1 Like

It’s probably because you need to use recursion.

Try implementing an algorithm with a time complexity of O(nlog(n))

Your algorithm is using an innner loop.
This increases the time complexity to O(n^2)
I would highly suggest figuring out how to refactor it to a superior time complexity of O(2n) or O(nlog(n))

I am referring to “Big Omicron” by the way aka Big-O notation.

If you have no clue what I’m talking about, learn it, deal with it, endure the pain of understanding it.