Project Euler Problem 10

JavaScript
1

Tell us what’s happening:
My code works fine on my machine. However, in fCC I the last test doesn’t work and it mentions a possible infinite loop (which it isn’t). On mine it runs all 4 tests in 0.6s.

Your code so far


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


let ans = 2;

for (let j = 3; j < n; j = j+2) {
  if (isPrime(j)) {
    ans += j;
  }
}
return ans;
}

Your browser information:

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

Challenge: Problem 10: Summation of primes

Link to the challenge:
https://www.freecodecamp.org/learn/coding-interview-prep/project-euler/problem-10-summation-of-primes

2

I’ve made it as efficient as I know how. I only check up to the square root for primes and I simply update a total rather than maintaining a large array and summing at the end. Any help is appreciated. Thanks.

3

Could you make isPrime more efficient if you had a list of all primes below num?

1 Like
4

I’m not sure. Currently each odd number below n goes through isPrime once. Rather than generating a list, I’m adding them to a running total. I think this should be less memory intensive than generating a list, but I could be wrong. I tried making ans an array, then summing it, but it took a little longer (~0.7s).

5

Thanks @JeremyLT. I added the line let s = Math.floor(Math.sqrt(num));, then replaced that part with s in the isPrime formula. That was enough to do it. It cut the time in half.

6

if you already have a list of primes it means you reduce the number of checks
for example, if you need to check if 101 is prime you would check only for 3,5 and 7, instead with your check it checks for 3,5,7 and 9
it is not much difference with low numbers, but primes become rarer in higher numbers, below 1 million there are ~80k primes

it is still enough to check till the square root of the number

you could try if in this way it is better

2 Likes
7

Ahh, okay. I now see what you mean by ‘list of primes’. I misunderstood the previous comment. That makes sense now. Thanks!

1 Like