Este é um problema muito interessante, tanto pelo entendimento do problema quanto pela implementação de uma solução. Pede-se para calcular o primeiro número triangular a possuir mais de 500 divisores. "Ah, mas é só ir gerando os números triangulares, passar o script que calcula o número de divisores, testar para ver se este número passa de 500, e pronto!". Bem, em teoria está correto. Porém, dá para melhorar - e muito.
Se você pegar um papel e um lápis, verá rapidamente que os números triangulares são somas de uma PA de razão 1 começando em 1. E mais: verá também que são (a partir do segundo número) a metade da multiplicação de um número par por um número impar. Agora, se a e b são números primos entre si, então n_divisores(a*b) = n_divisores(a) * n_divisores(b). A prova é um exercício para o leitor. Pode-se ver, também, que os dois fatores que compõem um número triangular > 1 são primos entre si. Portanto, com isso em mente, podemos construir um algoritmo que calcula a quantidade de divisores de números bem menores que cada número triangular, e usar o resultado para o mesmo efeito.
Este problema do PE é um caso em que usar a força bruta é uma péssima idéia. :o) No meu computador, esta solução foi encontrada em 44,88 segundos, enquanto uma versão em força bruta do mesmo algoritmo (calculando diretamente o número de divisores de cada número triangular) levou 7,31 minutos...
Nenhum comentário:
Postar um comentário