Project Euler Problems 1 to 100 - Problem 10: Summation of primes

Project Euler
1

Tell us what’s happening:

Here, I have to find the sum of every prime number under n. I tried this, but the console keeps printing “Potential infinity loop…”. I understand that I need to make the code more efficient, but I don’t understand how to do it (maybe changing the increment ?)

The other comment is for debugging, don’t mind it

Your code so far

function primeSummation(n) {
  let primes = [2]
  let sum = 2
  outerLoop : for (let i = 3; i < n; i += 2) { //Maybe I should change the increment
    for (const k of primes) {
      if (i % k === 0) {
        continue outerLoop
      }
    }
    primes.push(i)
    sum += i
  }
  //console.log(range, primes, sum)
  
  return sum;
}

console.log(primeSummation(2000000))

Your browser information:

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

Challenge Information:

Project Euler Problems 1 to 100 - Problem 10: Summation of primes

2

Potential infinity loop… is not only displayed when there’s infinite loop, but also when something takes a long time. There’s time limit for running individual tests, and when that limit is passed, test fails.

Time that takes for test to run can be sometimes artificially inflated by including in the code itself one of the hard test cases - ie. the line console.log(primeSummation(2000000)) will be executed each time the test is run. Removing that line still won’t make last of the tests pass. It needs additional optimizations to make it efficient enough.

I can tell that your general idea here is fine. Try to think of a way to end check of prime candidate earlier, some help with that might give logging to console and analyzing what checks happen exactly for what number.

1 Like
3

Here’s my new code with a console.log :

function primeSummation(n) {
  
  let primes = [2]
  let sum = 2
  outerLoop : for (let i = 3; i < n; i += 2) { 
    for (const k of primes) {
      console.log(`${i} % ${k} = ${i % k}`) //I added this
      if (i % k === 0) {
        continue outerLoop
      }
    }
    primes.push(i)
    sum += i
  }
  
  return sum;
}

console.log(primeSummation(17)) //Here I changed to 17 because it is not causing an error, so we can see the integrality of the tests

But I don’t see how to optimize it. I think that a prime number is a number that can only be divided by 1 and himself, so we have to iterate over every other prime, right ? And other than this, I can’t see any other optimization.

4

Well, yeah. The question is, whether prime candidate literally needs to be checked against every lower prime.

5

Hi @Jarvis_T ,

I have a note in some code I wrote to get primes…maybe this will help:

// Math.sqrt() makes this efficient by stopping the loop at the square root of num
// and the incrementor, i += 2, makes sure only odd numbers are evaluated
  for (let i = 3; i <= Math.sqrt(num); i += 2) {

Happy coding!

6

Hi @dhess ,

I don’t really understand. Here, there is :

what is num exactly? Is it the same thing that n? Because when I try :

for (let i = 3; i <= Math.sqrt(n); i += 2)

It completely fails (for n = 17, the loop stops at i = 5, which is not intended, it should stop at i = 15)

7

I’m unfamiliar with Project Euler, but your code looked similar to my code, which takes a number and eventually returns the sum of all primes less than or equal to the number. The bit I shared was from a helper function used to determine if a number is prime.

1 Like
8

Thank you a lot @dhess and @sanity , I could pass the test (with your bit of code, dhess). I won’t display the solution (for obvious reasons :wink: ), but I managed through it with your help. Thank you again !