Sum All Primes - 7/17/2018

Sum All Primes - 7/17/2018
0

#1

Tell us what’s happening:
Hey fellow campers, thanks for all the help so far, this community is great.

I’m not sure if this is another copy & paste problem? When I run this code in Visual Studio, everything works fine, but then when I try to run in FCC, the code doesn’t run at all.

Anyone know what’s going on?

Your code so far


function sumPrimes(num) {

    let sum = 0;

    const isPrime = n => {
        for (let i = 2; i < n; i++)
            if (n % i === 0) return false;
        return n !== 1;
    }

    for (i = 2; i <= num; i++) {
        if (isPrime(i)) {
            sum += i;
            console.log(i);
            console.log(isPrime(i));
        }
    }

    console.log(sum);
    return sum;
}

// test here
sumPrimes(10);

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/67.0.3396.99 Safari/537.36.

Link to the challenge:
https://learn.freecodecamp.org/javascript-algorithms-and-data-structures/intermediate-algorithm-scripting/sum-all-primes


#2

missing brackets around “n” in const isPrime should be a problem in function declaration. its should look like const isPrime = (n) => {...}


#3

@StanSkrivanek Hey Stan, thanks for the suggestion. The code worked fine in Visual Studio without the parenthesis. I tried putting them in on FCC but still wasn’t able to run.


#4

It is because your algorithm is not as fast as the tests will accept. At some point during processing of your code, the code stops executing. See if you can do some research on how to develop an algorithm which is more efficient.


#5

Interesting, thanks.


#6

I updated the code with an array instead of a sum+=sum, but still didn’t run for some reason. I looked at some other posts on the forum and found this one.

Interestingly enough, my code is the exact same algorithm as this one, yet when I use the one on this post, the tests run. However, when I use the original code I had, the tests do not run. I’m thinking it may be a copy / paste issue with an invisible character like the last one. Not sure.

Anyways, moving on to the next one, thanks.


#7

I realise you’ve moved on but I wanted to share how I reduced the complexity of my program. Basically I used 3 divisibility rules which more than cut my set of numbers down in half.
The obvious only is divisble by 2 (if the num > 2 and even, then it is not a prime).
The second one is divisible by 3 rule ( if the num > 3 , you add all the digits in the number and if that value is divisible by 3 then it is not a prime)
The last one is the divisible by 5 (num > 5 and its unit digit ends with 5. Note; I already eliminated even numbers so I didn’t have to check of ends with 0).

These three seemed to do the trick for my program speed…


#8

It’s worth redoing this one and holding onto a quality prime number generator

You’ll thank yourself later with some of the project Euler questions

My recommendation would be the sieve of Eratosthenes, it’s simple, old, and has some straightforward modifications that make it quite performant


#9

Thanks for both the suggestions. I saw the hint used the sieve algorithm but was blocked out. I’ll research that one and see if I can understand how that works.


#10

OK, so I’m back on sum of all primes. I will say this, I am very thankful there are people out there who can write these mathematical algorithms - I certainly cannot write these, but I do appreciate them greatly.

I found this algorithm on stackoverflow and is working except for including the provided number. Anyone have any clues on how to do this?

[spoiler] var eratosthenes = function (n) {
// Eratosthenes algorithm to find all primes under n
var array = [], upperLimit = Math.sqrt(n), output = [2];

    // Make an array from 2 to (n - 1)
    for (var i = 0; i < n; i++)
        array.push(1);

    // Remove multiples of primes starting from 2, 3, 5,...
    for (var i = 3; i <= upperLimit; i += 2) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i * 2)
                array[j] = 0;
        }
    }

    // All array[i] set to 1 (true) are primes
    for (var i = 3; i < n; i += 2) {
        if (array[i]) {
            output.push(i);
        }
    }[/spoiler]

Also is anyone able to explain this block in as simple as possible terms? Making the array with true or false I understand. I’m not clear on why we make the loop like this: for (var j = i * i; j < n; j += i * 2) ?

    // Remove multiples of primes starting from 2, 3, 5,...
    for (var i = 3; i <= upperLimit; i += 2) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i * 2)
                array[j] = 0;
        }
    }

#11

Alright, first this:

working except for including the provided number

comes from this:

// Make an array from 2 to (n-1)

which shows clearly that it’s generating the primes below n. If you want the primes including n just call the function with n+1


Now the harder part to explain, I’m not the best at explaining things but I’ll try, so bear with me

for(var j = i * i; j < n; j += i*2) comes from a combination of facts that let us cut down on the number of things we need to do

Firstly, lets talk about the j = i * i:
This comes from the observation that you don’t need to ‘cross off’ any numbers below the square of a prime, as they’ll already have been crossed off by primes less than it, so we can start crossing off numbers from the current prime squared.

Secondly, no even numbers are prime except 2, this fact was used earlier in your code to use i += 2 in the loop, literally halfing the numbers we have to check.

That second fact is also used here: j += i * 2
In the traditional sieve, you cross out every multiple of the prime. However, if i is odd, which is always is for us, and j starts out odd, then j + (odd number) * i will be even, and thus pointless for us to cross out as we already know it can’t be prime

Let me know if that helps at all or is confusing in any way


#12

@gebulmer Thanks gebulmer, that was great. I realized after you said adding n+1, I had tried this but simply put the +1 in the wrong place. Put it in the functino(n+1) instead of when I initially call the function.

*sum = eratosthenes(num + 1);

*I realized this is where the +1 needs to go.

As for the second part, I’m still trying to get my head around this. I’m a visual learned and the wiki helps -

I’m at the point where I understand what the code is doing, but I don’t understand this well enough to write something like this myself. My brain has trouble holding all these numbers in my head haha.

At least I have a base understanding and I’m sure I’ll see this again. Code and reiterate, code and reiterate. I think after I do this enough times I’ll understand better, thanks.


#13

There’s a lot of spooky mathemagic when it comes to optimisation of algorithms, I’d probably start with writing the traditional sieve of eratosthenes yourself from Wikipedia’s pseudocode description

Worry later about the improvements I mentioned in the previous post, and they’re something you can ‘add-on’ to a basic traditional version later when it becomes more ‘obvious’

But don’t worry about it!

(There’s another cool trick called Wheel Factorisation which is a generalisation of the skipping all even numbers trick)


#14

Haha great, thanks! I have a feeling there is an infinite amount of knowledge here to learn, so I’ll need to stay focused on what I need for the current project and try not to go down any “rabbit-holes” for unnecessary knowledge.

I’m sure all of the extra stuff is fun and interesting, but at the same time my brain can only hold so much information at one time.

Thanks again @gebulmer