# Help optimizing code in Project Euler 12

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

``````
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
}
``````

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

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.

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

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
}
``````

1 Like

That helped a lot. Thanks!

1 Like