<Algorithms >Divisor Problem

Given a the number of divisors, we have to find the first triangle number.

A triangle number is same as sum of natural numbers.

I had adopted the method of taking prime numbers starting from 2 and permute them so that the number generated matches triangle number.

For example, suppose we are given 5 divisors. I take primes starting from 2 onwards (2,3,5) as N=p1^a1*p2*a2*p3^a3. Number of divisors are (a1+1)(a2+1).... 开发者_如何学JAVAhere 2,3,5 can take powers and permuted. Then n^2+n=2k (k is the value got from permutation). I check n value to be Integer.

I have not found any efficient algo besides this, does any one has more optimal one?

You can use reverse approach. Since n-th triangle number can be found as (n^2 + n)/2, you can just iterate n and for each number count its divisors. Some optimizations:

• (n^2+n)/2 = n(n+1)/2. n and n+1 do not have any common divisors (except for 1), and only one of them is even. Therefore the number of divisors is either multiplied number of divisors of n/2 and n+1, or multiplied number of divisors of n and (n+1)/2.
• number of divisors can be found by the formula you mentioned, therefore you only need a list of prime numbers (get it here, for example)

This approach seems to be a bit more straightforward and optimal. Moreover, it guarantees that you will find the first triangle number.