Para somar os dígitos, converta o número para uma string.
O programa a seguir exige um pouco de matemática. Ele roda em 0,348 ms em uma máquina Core2Duo 1.86 GHz.
[code]
import java.util.Map;
import java.util.HashMap;
class Problema12ProjectEuler {
private Map<Integer,Integer> nDiv = new HashMap<Integer,Integer>();
// Bastante ingênuo mas um pouquinho otimizado...
private int nDivisores (int n) {
if (nDiv.containsKey (Integer.valueOf (n)))
return nDiv.get (n);
else {
int resultado = 1;
for (int i = 2; i <= n; ++i) {
if (n % i == 0)
resultado++;
}
nDiv.put (n, resultado);
return resultado;
}
}
public int nDivisoresTriangular;
public int nTriangular (int nMinDivisores) {
int n = 1;
nDivisoresTriangular = 0;
do {
n++;
if (n % 2 == 0) {
nDivisoresTriangular = nDivisores (n / 2) * nDivisores (n+1);
} else {
nDivisoresTriangular = nDivisores (n) * nDivisores ((n+1) / 2);
}
} while (nDivisoresTriangular < nMinDivisores);
return n * (n + 1) / 2;
}
public static void main(String[] args) {
Problema12ProjectEuler e = new Problema12ProjectEuler();
// Note que um número triangular n(n+1)/2 é composto de 2 números, n e n+1/2.
// Devemos então determinar o número de divisores de n, de n+1/2, e então multiplicá-los.
// Isso dará o número de divisores de n(n+1)/2.
System.out.println ("O numero de divisores do numero triangular " + e.nTriangular (5) + " eh " +
e.nDivisoresTriangular);
long t = System.currentTimeMillis();
int resultado = e.nTriangular (500);
t = System.currentTimeMillis() - t;
System.out.println (“O numero de divisores do numero triangular " +
resultado + " eh " + e.nDivisoresTriangular + " e foi calculado em " + t + " ms”);
}
}[/code]
Por que você testa se o número é par dentro do while?
Quer dizer, vi que vc só divide o lado par da equação por 2.
Seria por precisão? Performance? Ou algum outro motivo que não visualizei?
Ah sim, claro, pq vc chama nDivisores, que tem como argumento um int.
A matemática que é necessário saber é :
- Se dois ou mais números são primos entre si, o número de divisores do seu produto é igual ao produto dos números de divisores de cada um;
- n e n+1 são primos entre si. Se n for par, isso implica em n/2 e n+1 serem primos entre si.
Como o thingol eu percebi que pra encontrar um número triangular é só usar a fórmula da soma dos termos de uma PA, mas não sabia da fórmula para achar o número de divisores de um número baseado nos expoentes de seus fatores. Com tal ajuda, fiz um programinha que ficou bastante parecido com o do thingol mas que, acreditem ou não, foi terminado antes dele postar o seu.
Aqui após 10 execuções o seu ficou com 359 ms de média e o meu com 274 ms. Entre a minha micro-vantagem no tempo e organização do seu código, eu fico com o seu. Fica como desafio pra alguém que queira otimizar mais ainda. O meu pode se alguém achar um jeito de evitar o Map e fazer a multiplicação da soma dos expoentes no mesmo loop.
[code]import java.util.HashMap;
import java.util.Map;
public class Divisor {
public static void main(String[] args) {
long ini = System.currentTimeMillis();
int d = 0;
int n = 1;
int nt = 2;
while (d < 500) {
nt = (n * (1 + n))/2;
d = numeroDeDivisores(nt);
n++;
}
System.out.println(nt + “\t” + d);
long fim = System.currentTimeMillis();
System.out.println("TEMPO: " + (fim - ini));
}
public static int numeroDeDivisores(int n) {
int divisores = 1;
Map<Integer, Integer> somas = new HashMap<Integer, Integer>();
while (n > 1) {
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
if (somas.containsKey(i)) {
somas.put(i, somas.get(i) + 1);
} else {
somas.put(i, 2);
}
n /= i;
break;
}
}
}
for (Integer i : somas.values()) {
divisores *= i;
}
return divisores;
}
}[/code]
O meu programa é mais lento que o do Ozix, obviamente porque o cálculo do número de divisores dele é mais otimizado.
Se juntar os dois programas deve ficar algo mais rápido ainda.
Juntei o do Ozix com o meu e deu 109 ms. Muito legal.
[code]
import java.util.Map;
import java.util.HashMap;
class Problema12ProjectEuler {
Map<Integer,Integer> nDiv = new HashMap<Integer,Integer>();
// Bastante ingênuo mas um pouquinho otimizado...
/*
private int nDivisores (int n) {
if (nDiv.containsKey (Integer.valueOf (n)))
return nDiv.get (n);
else {
int resultado = 1;
for (int i = 2; i <= n; ++i) {
if (n % i == 0)
resultado++;
}
nDiv.put (n, resultado);
return resultado;
}
}
*/
public int nDivisores (int n) {
if (nDiv.containsKey (Integer.valueOf (n)))
return nDiv.get (n);
else {
int m = n;
int divisores = 1;
Map<Integer, Integer> somas = new HashMap<Integer, Integer>();
while (n > 1) {
for (int i = 2; i <= n; i++) {
if (n % i == 0) {
if (somas.containsKey(i)) {
somas.put(i, somas.get(i) + 1);
} else {
somas.put(i, 2);
}
n /= i;
break;
}
}
}
for (Integer i : somas.values()) {
divisores *= i;
}
nDiv.put (m, divisores);
return divisores;
}
}
public int nDivisoresTriangular;
public int nTriangular (int nMinDivisores) {
int n = 1;
nDivisoresTriangular = 0;
do {
n++;
if (n % 2 == 0) {
nDivisoresTriangular = nDivisores (n / 2) * nDivisores (n+1);
} else {
nDivisoresTriangular = nDivisores (n) * nDivisores ((n+1) / 2);
}
} while (nDivisoresTriangular < nMinDivisores);
return n * (n + 1) / 2;
}
public static void main(String[] args) {
Problema12ProjectEuler e = new Problema12ProjectEuler();
// Note que um número triangular n(n+1)/2 é composto de 2 números, n e n+1/2.
// Devemos então determinar o número de divisores de n, de n+1/2, e então multiplicá-los.
// Isso dará o número de divisores de n(n+1)/2.
System.out.println ("O numero de divisores do numero triangular " + e.nTriangular (5) + " eh " +
e.nDivisoresTriangular);
long t = System.currentTimeMillis();
int resultado = e.nTriangular (500);
t = System.currentTimeMillis() - t;
System.out.println (“O numero de divisores do numero triangular " +
resultado + " eh " + e.nDivisoresTriangular + " e foi calculado em " + t + " ms”);
}
}[/code]
Eu só faria uma alteração.
O que é mais rápido: fazer uma divisão ou deslocar um bit?
Calcular o módulo de uma divisão ou fazer um E a nível de bit?
Creio que a segunda opção em cada caso, não?
Que tal, ao invés de dividir por dois, deslocar um bit para a direita?
return n * ((n + 1) >> 1);E fazer um E lógico?
if (((n & 1) == 0) {Claro que são mudanças sutis (quase insignificativas quando rodando nas máquinas atuais), mas em grandes laços podem fazer alguma diferença. 
Marco, eu fiz as modificações sugeridas, e não vi diferença alguma. Acho que é porque a JVM já faz essas otimizações (trocar divisões por shifts se for o caso) transparentemente.
Legal. Mais uma vez, a colaboração vence. Modifiquei o método nDivisores() para não usar Map. Imaginei que não usando objetos seria mais rápido, mas aqui não houve melhora no desempenho:
[code] public int nDivisores(int n) {
int divisores = 1;
int fator = 2;
while (n > 1) {
int soma = 1;
int t = n % fator;
while (t == 0) {
soma++;
n /= fator;
t = n % fator;
}
divisores *= soma;
fator++;
}
return divisores;
}[/code]Acabei de perceber que o “t” ali em cima está à toa. Agora sim, melhorou um pouquinho:
[code] public int nDivisores(int n) {
int divisores = 1;
int fator = 2;
while (n > 1) {
int soma = 1;
while (n % fator == 0) {
soma++;
n /= fator;
}
divisores *= soma;
fator++;
}
return divisores;
}[/code]no caso do outro problema… de somar os digitos do fatoria de um numero…
para fazer o fatorial é simples… ja fiz, depois tem que converter para string… pode ser através do
String.valueOf(x); ?? sendo que x é o resultado do fatorial…
e para soma os digitos??
digamos que é 5!.. o resultado é 120
eu tenho que fazer 1+2+0
Você fez direitinho o fatorial? 100! é um número de 157 dígitos, e começa por 9332621544394415268169923885626…
Se não for esse número então você não fez direito o fatorial.
EDIT - A propósito, se seu programa funcionar direitinho, a resposta para “soma dos dígitos” é 648. Só para você conferir se você fez tudo direitinho mesmo.
Ainda no problema anterior, usando um array com os 1476 primeiros números primos (eu sei, é bem específico pra esse problema) eu consegui rodar o programa em 15 ms! Sem o array consegui fazer um tempo de 72 ms.
que ferramenta vcs utilizam para medir a velocidade de execução utilizo o netbeans e o tempo de execução so calcula a partir de segundos
Use System.currentTimeMillis () ou System.nanoTime().