Optimización programa básico

[HelThunder]

   public static int numeroDivisores(int n){
      int n =0 ;
      for (int i=1;i<=n;++i){
         if (n%i==0){
            ++n;
         }
      }
      return n;
   }

He hecho ese método para hallar el número de divisores de un número. Pero necesita hacerlo de alguna forma mejor que lleve menos tiempo para compilar. Ya que invoco muchas veces este método en otro método y con cifras grandes tarda mucho tiempo.

¿Alguien sabria alguna forma de optimizar este metodo?

Un saludo, gracias.

[1mpuls0]

Código (java) [Seleccionar] Expandir


/*Autor: 1mpuls0*/

public class NumberOfDivisors {
   
   public static void main(String args[]){
       long start = 0;
       long end = 0;
       int number = 420;
       
       start = System.nanoTime();
       System.out.println("Number of divisors " + number + ": " + countDivisors(number ));
       end = System.nanoTime();
       System.out.println("Execution time was " +(end-start)+" ns");
       
       
       start = System.nanoTime();
       System.out.println("Number of divisors " + number + ": " + countDivisors2(number ));
       end = System.nanoTime();
       System.out.println("Execution time was "+(end-start)+" ns");

   }
   
   public static int countDivisors(int number){
       int count = 0 ;
       
       for (int index = 1; index<=number; ++index){
           if (number%index==0){
               ++count;
           }
       }
       return count;
   }
   
   public static int countDivisors2(int number) {
       int index = 1;
       int count = 0 ;

       int div_2 = (int)Math.sqrt(number) + 1;
       while(index < div_2){
           if(number % index ==  0 ){
               count++;
           }
           index++;
       }

       if(count > 1){
           while(number >= index){
               if(number % index ==  0){
                   count++;
               }
               index++;
           }
       }

       return count;
   }
}


[HelThunder]

Muchísimas gracias Darhius, pero el nuevo método no me mejora el problema, me explico. Por lo que entiendo, tu codigo reduce el tiempo ya que descarta los numeros con pocos divisores ahorrando operaciones. Lo que pasa, es que en el programa en que utilizo este método, tengo que ir mirando los divisores de millones de numeros, y todos ellos son muy grandes, por lo que la condición que has puesto, tan apenas quita procesos.

Incluso tarda más el programa en ejecutarse.

Los tiempos de ejecución han sido los siguientes;

Aclaro que me refiero a la ejecución del programa completo, que invoca a este método y a otro.

Número	countDivisors	countDivisors 2
6	513	80052
125	285160592	376253252
200	13414467371	14718342716

No acabo de entender a que se debe esto siendo que independentientes, el 2º es más rapido.

Muchas gracias  

[1mpuls0]

Me imaginé que no solo era para contar los divisores.
Seguiré analizando una alternativa para ver que se puede hacer.

Saludos.

[kaostias]

Si los números que utilizas pueden repetirse y tienen alta tendencia a hacerlo, puedes crear una tabla hash que vaya guardando los resultados para cada número, la primera vez que lo ejecutes siempre hará el cálculo, pero a partir de ahí el acceso tiene coste constante.

[egyware]

**coff** **coff*

Programación dinámica

**coff** **coff*