Help optimizing code in Project Euler 12

JavaScript
1

Tell us what’s happening:
The code is very slow and so fails the last 2 tests. Please help me optimise it

Your code so far


function divisibleTriangleNumber(n) {
  let i=n+"".length, currentNatural=1
  while(numberOfFactors(currentNatural)<n) {
    currentNatural=i*(i+1)/2
    i++
  }
  return currentNatural
}

function numberOfFactors(n) {
  let f=0
  for(let i=2; i<n/2; i++)
    if(n%i==0)
      f++
  return f+2
}

Your browser information:

User Agent is: Mozilla/5.0 (Windows NT 6.1; ) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/81.0.4044.138 Safari/537.36.

Challenge: Problem 12: Highly divisible triangular number

Link to the challenge:

2

You’ve got the right idea, but you aren’t being aggressive enough. n/2 is roughly as bad as n. But the biggest factor, other than n, is much smaller. You have to be careful about how you count, but you only need to check sqrt(n) values to count the factors.

3

I played with it and

function numberOfFactors(n) {
  let count=2
  let i=2
  while(i**2<n) {
    if (n % i == 0)
      // Because factors come in pairs
      count += 2
    i += 1
  }
  if (i**2==n)
    count++
  return count
}

worked. But I don’t understand how it works

4

I would make a small tweak:

function numberOfFactors(n) {
  let count=2
  let i=2
  // Single bound computation is faster
  const bound = math.floor(math.sqrt(n))
  // Check i from 2 to largest possible factor
  while(i < bound) {
    if (n % i == 0)
      // Because factors come in pairs
      //   if i is a factor, n/i is too
      count += 2
    i += 1
  }
  // If n = i*i, then we only want to count
  //   the factor i once
  if (i**2==n)
    count++
  return count
}

I added a couple of comments that maybe help explain things?

1 Like
5

That helped a lot. Thanks!

1 Like
6