Download Enunciado La secuencia de números triangulares se genera

Enunciado
La secuencia de números triangulares se genera sumando los números naturales. Por tanto, el 7mo. Número triangularsería 1 + 2 + 3 + 4 + 5
+ 6 + 7 = 28. Los primeros diez números triangulares son:
1, 3 6, 15 21, 28, 36, 45, 55
Listemos los factores de los primeros siete números triangulares:
1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28
Podemos ver que 28 es el primer número triangular que tiene más de cinco divisores. ¿Cuál es el valor del primer número triangular que
tiene más de quinientos divisores?
[Fuente: projecteuler.net]
Solución
Redactamos una función que recibe en un int la cantidad de divisores tope y retorna en un long el primer número que supera a esa
cantidad de divisores. Para ello inicializamos un contador en 1 y dentro de un ciclo while invocamos una función que nos retorne el número
triangular correspondiente y a otra función que nos dé la cantidad de factores de ese número triangular.
Si la cantidad de factores supera al valor recibido, bajamos la bandera y asignamos al número buscado el valor del número triangular que
resultó tener tantos factores, abandonamos el ciclo y retornamos el valor buscado.
long priNatMasFac(int t)
{
// primer natural con más de t factores (incluyendo a 1 y a él mismo)
long p; // primero - número buscado
long k = 1; // contador para obtener números triangulares
long tr; // número triangular correspondiente a k
long c = 1; // cantidad de factores números correspondiente a tr
int flg = 1; // bandera indica sigue buscando
while (flg)
{
tr = numTri(k);
c = canFac(tr);
if (c > t)
{
p = tr;
flg = 0;
}
k++;
}
return p;
}
long numTri(long n)
{
// número triangular correspondiente a n (1+2+ … +n)
long t = n*(n+1)/2;
return t;
}
int canFac(long n)
{
// cantidad de factores (divisores) de n, incluyendo a 1 y a n
int c = 2; // cantidad factores (ya contados a 1 y a n)
long d; // posibles divisors de n
for (d = 2; d <= n/2; d++)
if (n % d == 0) c++;
return c;
}
Note que la función numTri() calcula bien rápido el número triangular, mediante una fórmula y no sumando los naturales de 1 a n. Pero la
función canFac() sí calcula a fuerza bruta la cantidad de factores de n, por lo que esta solución no es la más eficiente. Sin embargo, basta
mejorar la eficiencia de la solución canFac() para que la eficiencia global sea buena.
Por ahora, no estamos interesados en algoritmos muy eficientes u óptimos, sino que encuentren una solución. Tal cosa estaría fuera de los
límites de este texto, si bien algunas soluciones planteadas aquí son aceptablemente eficientes.
ecabrera, 2011, octubre