This week's book giveaway is in the Design forum. We're giving away four copies of Building Microservices and have Sam Newman on-line! See this thread for details.

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

As always, the code is not generating a result, should I use BigInteger instead of long? is there a better way to do this?

Hate the point out the obvious, but you really need to learn how to debug a program. This problem as with the other "always" programs can be debugged with some interium results printouts within the loop.

@Campbell Ritchie the counter is reset to zero to count how many divisors each number has, or else we will be counting the sum of divisors for all the numbers

@Henry Wong this code works for small numbers, but when the numbers get large, each loop will loop twice to that number which will take forever to end... but I cant figure any other way to do this

The loop termination condition can be changed to j<= triNbr/2.

Reasoning- You don't have to check for divisors of a number N in the range (N/2)+1 ... N as there are never going to be any, except for the number N itself.

A further optimization could be made when N is not an even number (i.e. it is an odd number).

Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89

posted

0

@Neelesh A Korade the triNbr/2 might help a little bit, but not much, since the loop is very large anyway...

and what if the number is odd? couldnt it have a 500 divisors if its odd? why?

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 44048

33

posted

0

It needs more optimisations than that; it is cubic complexity and runs in O(n^3) time. You need to work out how to reduce the counting space.

So 1 and N are divisors of N: Right, start from potentialDivisor = 2 and divisorCount = 2. If it divides by 2, there will be a 2nd divisor, N / 2, and if it divides by 3 there will also be N / 3.

Work out how to terminate your loop and reduce the complexity. Otherwise it will take all day to run.