Programa que conte numeros triangulares

X! >= 500

Achando X, você já sabe o que fazer

Até!

enquanto o número de divisores for menor que 500 faça NT = próximo número triangular; fatore NT; calcule e conte o número de divisores de NT; fim;

Já deste uma analisada no seu algoritmo?
Fatorar um número não é algo que se faça em 2 segundos. Acho melhor ele estudar um pouco de álgebra e reduzir esse problema a achar qual é o menor número com 500 divisores e apartir dele achar o número triangular com 500 ou mais divisores.

Dessa maneira ele vai rodar o programa e vai ter a resposta no outro dia.

Até!

nao fui eu que fiz este algoritimo, ele é apenas um exemplop dado pelo professor, que faz parte do problema… de qualquer maneira obrigado…

tem outro aqui que não entendi muito bem mas parece mais simples, se alguem pudesse me ajudar também:

Encontrar a soma dos digitos de 100!

vlw

Cara, esse problema dos números tringulares te exige mto mais conhecimento matemático do que de programação. Fiz um algoritmo que é semi força bruta, consegui elaborar uns meios de ignorar alguns cálculos desnecessários, mas, mesmo assim ainda demora mtoooo.

Pra ti ter uma ideia, minha máquina (rodando o algoritmo nesse momento) ta nesse número triangular aqui 7556328 e ainda tem só 148 divisores se não me engano =P. Imagina o tamanho desse número que teu professor quer achar.

Nem sei se ainda estas interessado nesse tópico…Se quizer o código me avisa.

Att.

Um número triangular é um número t = n (n + 1) / 2, sendo n >= 0. Por exemplo, se n = 7, então t = 56.

O número de divisores de um número t pode ser determinado fatorando o número. Digamos que um número t tenha os fatores primos a, b e c.

t = a^x . b^y . c^z

Então o número de divisores é dado por (x+1).(y+1).(z+1).

Por exemplo, se t = 18907875 = 3^2 . 5^3 . 7^5, então ele tem 3 . 4 . 6 = 72 divisores.

O menor número que tem mais de 500 divisores é 14414400, que é 2^6 . 3^2 . 5^2 . 7 . 11 . 13 e tem 504 divisores.
Infelizmente esse número não é triangular.
Uma forma de achar um número triangular com 504 divisores é procurar um número que tenha 6 fatores primos , elevados às potências 6, 2, 2, 1, 1, e 1 respectivamente, e que também seja triangular (ou seja, ele é da forma n(n+1)/2)
mais ou menos como se fosse o número 14414400.

rsoliveira

sim, estou interessado ainda…

pode passar o codigo… mas o professor falou…

tem q rodar em 5 segundos

oO
mas pode mandar ai…

JaVa_MaChInE:

nao fui eu que fiz este algoritimo, ele é apenas um exemplop dado pelo professor, que faz parte do problema… de qualquer maneira obrigado…

tem outro aqui que não entendi muito bem mas parece mais simples, se alguem pudesse me ajudar também:

Encontrar a soma dos digitos de 100!

vlw

A soma dos dígitos de 100! pode ser feita por força bruta; basta usar BigDecimal e calcular o fatorial da forma convencional (ou seja, 1 . 2 . 3 . … . 100).

JaVa_MaChInE:

rsoliveira

sim, estou interessado ainda…

pode passar o codigo… mas o professor falou…

tem q rodar em 5 segundos

oO
mas pode mandar ai…

5 segundos!? =O

Então meu código não vai servir pra nada xD

Tava dando uma olhada nas explicações que nosso amigo moderador estava dando a respeito dos números triangulares e vou tentar fazer outro algoritmo, mas, não agora pq tô no trabalho.

Assim que der eu tento fazer o/

Att.

Para rodar em menos de 5 segundos, você vai ter que achar algum truque matemático para determinar o número de divisores sem fatorá-lo.

De fato, ele diz que tem que ter 500 divisores, mas você não precisa saber quais.

rsoliveira
oo… mas pode mandae seu codigo ai… e vlw pela ajuda

esse é o problema 12 do Project Euler.

http://projecteuler.net/index.php?section=problems&id=12

maquiavelbona:

Já deste uma analisada no seu algoritmo?
Fatorar um número não é algo que se faça em 2 segundos. Acho melhor ele estudar um pouco de álgebra e reduzir esse problema a achar qual é o menor número com 500 divisores e apartir dele achar o número triangular com 500 ou mais divisores.

Dessa maneira ele vai rodar o programa e vai ter a resposta no outro dia.

Até!

O número 76576500 tem 576 divisores, e é um número triangular (n = 12375).

JaVa_MaChInE:

nao fui eu que fiz este algoritimo, ele é apenas um exemplop dado pelo professor, que faz parte do problema… de qualquer maneira obrigado…

tem outro aqui que não entendi muito bem mas parece mais simples, se alguem pudesse me ajudar também:

Encontrar a soma dos digitos de 100!

vlw

Fiz aqui a soma dos dígitos de 100!, e deu 648.

Dica: usei BigInteger

a soma dos digitos de 100! da para fazer com um for??

Dá para fazer com 2 fors - um para calcular 100!, e outro para somar os dígitos.

10! tranqulio consegui fazer de boa… mas a soma dos digitos dele???

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.

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");
    }
}

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.

thingol:

roda em 0,348 ms

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;
   }
}

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.

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");
    }
}

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.

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().