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.
Your code so far
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);
Your browser information:
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.
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);
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.
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.
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.
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.
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.