Obteniendo Factores de un Número

Question

Problema: Estoy tratando de refactorizar este algoritmo para hacerlo más rápido. ¿Cuál sería la primera refactorización aquí para la velocidad?

public int GetHowManyFactors(int numberToCheck) 
    { 
     // we know 1 is a factor and the numberToCheck 
     int factorCount = 2; 
     // start from 2 as we know 1 is a factor, and less than as numberToCheck is a factor 
     for (int i = 2; i < numberToCheck; i++) 
     { 
      if (numberToCheck % i == 0) 
       factorCount++; 
     } 
     return factorCount; 
    } 

Answer 1

La primera optimización que puede hacer es que solo necesita verificar la raíz cuadrada del número. Esto se debe a que los factores vienen en pares, donde uno es menor que la raíz cuadrada y el otro es mayor.

Una excepción a esto es si n es un cuadrado exacto, entonces su raíz cuadrada es un factor de n pero no es parte de un par.

Por ejemplo si su número es 30 los factores son en estos pares:

• 1 x 30
• 2 x 15
• 3 x 10
• 5 x 6

Por lo tanto, no es necesario que marque ningún número superior a 5 porque ya se puede deducir que existen todos los demás factores una vez que encuentra el factor pequeño correspondiente en el par.

Aquí es una manera de hacerlo en C#:

public int GetFactorCount(int numberToCheck) 
{ 
    int factorCount = 0; 
    int sqrt = (int)Math.Ceiling(Math.Sqrt(numberToCheck)); 

    // Start from 1 as we want our method to also work when numberToCheck is 0 or 1. 
    for (int i = 1; i < sqrt; i++) 
    { 
     if (numberToCheck % i == 0) 
     { 
      factorCount += 2; // We found a pair of factors. 
     } 
    } 

    // Check if our number is an exact square. 
    if (sqrt * sqrt == numberToCheck) 
    { 
     factorCount++; 
    } 

    return factorCount; 
} 

Hay otros enfoques que podría utilizar que son más rápidos, pero puede encontrarse con que esto ya es lo suficientemente rápido para sus necesidades, especialmente si sólo se necesita para trabajar con enteros de 32 bits.

Answer 2

Reducir el límite de lo alto que tiene que ir ya que podría a sabiendas parar en la raíz cuadrada del número, aunque esto lleve la precaución de escoger las plazas que tendría el número impar de factores, pero sí ayuda a reducir la frecuencia con la que se debe ejecutar el ciclo.

Answer 3

1. Puede limitar el límite superior de su bucle FOR a numberToCheck/2

2. Comience el contador de bucle a las 2 (si el número es par) o 3 (para valores impares). Esto debería permitirle verificar cada otro número disminuyendo su conteo de bucles en otro 50%.

   public int GetHowManyFactors(int numberToCheck) 
   { 
       // we know 1 is a factor and the numberToCheck 
       int factorCount = 2; 
   
       int i = 2 + (numberToCheck % 2); //start at 2 (or 3 if numberToCheck is odd) 
   
       for(; i < numberToCheck/2; i+=2) 
       { 
       if (numberToCheck % i == 0) 
        factorCount++; 
       } 
       return factorCount; 
   } 
   

Answer 4

Parece que hay una larga discusión sobre este tema exacto aquí: Algorithm to calculate the number of divisors of a given number

espero que esto ayude

Answer 5

Bueno, si usted va a utilizar mucho esta función se puede utilizar modificada algoritmo de Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes y almacenar answars para un intervalo de 1 a Max en la matriz. Ejecutará IntializeArray() una vez y después devolverá las respuestas en 0 (1).

const int Max =1000000; 
int arr [] = new int [Max+1]; 

public void InitializeArray() 
{ 
    for(int i=1;i<=Max;++i) 
     arr[i]=1;//1 is factor for everyone 

    for(int i=2;i<=Max;++i) 
     for(int j=i;i<=Max;i+=j) 
      ++arr[j]; 
} 
public int GetHowManyFactors(int numberToCheck) 
{ 
    return arr[numberToCheck]; 
} 

Pero si no vas a utilizar esta función mucho, creo que la mejor solución es comprobar la raíz cuadrada de unitll.

---

Nota: ¡He corregido mi código!

Answer 6

Lo primero que debe tener en cuenta es que es suficiente para encontrar todos los factores primos. Una vez que tenga estos, es fácil encontrar la cantidad de divisores totales: para cada primo, agregue 1 a la cantidad de veces que aparece y multiplíquelos. Entonces para 12 = 2 * 2 * 3 tienes (2 + 1) * (1 + 1) = 3 * 2 = 6 factores.

Lo siguiente se sigue del primero: cuando encuentre un factor, divídalo para que el número resultante sea más pequeño. Cuando combina esto con el hecho de que solo necesita verificar la raíz cuadrada del número actual, esta es una gran mejora. Por ejemplo, considere N = 10714293844487412. Ingenuamente tomaría N pasos. Verificar hasta su raíz cuadrada requiere sqrt (N) o aproximadamente 100 millones de pasos. Pero dado que los factores 2, 2, 3 y 953 se descubren desde el principio, en realidad solo se necesita consultar un millón: ¡una mejora de 100 veces!

Otra mejora: no necesita verificar cada número para ver si divide su número, solo los números primos. Si es más conveniente, puede usar 2 y los números impares, o 2, 3, y los números 6n-1 y 6n + 1 (un tamiz de rueda básico).

Aquí hay otra buena mejora. Si puede determinar rápidamente si un número es primordial, puede reducir aún más la necesidad de división. Supongamos que, después de eliminar factores pequeños, tiene 120528291333090808192969. Incluso el chequeo hasta su raíz cuadrada llevará mucho tiempo: 300 mil millones de pasos. Pero una prueba de Miller-Rabin (muy rápido, quizás de 10 a 20 nanosegundos) mostrará que este número es compuesto. ¿Cómo ayuda esto? Significa que si revisas su raíz cúbica y no encuentras factores, entonces quedan exactamente dos primos. Si el número es un cuadrado, sus factores son primos; si el número no es un cuadrado, los números son primos distintos. Esto significa que puede multiplicar su "total acumulado" por 3 o 4, respectivamente, para obtener la respuesta final, ¡incluso sin conocer los factores! Esto puede marcar más una diferencia de lo que imaginaba: la cantidad de pasos necesarios pasa de 300 mil millones a solo 50 millones, ¡una mejora de 6000!

El único problema con lo anterior es que Miller-Rabin solo puede probar que los números son compuestos; si se le da un primo no puede probar que el número es primo. En ese caso, puede escribir una función de prueba de primalidad para ahorrarse el esfuerzo de factorizar a la raíz cuadrada del número. (Alternativamente, podría hacer algunas pruebas más de Miller-Rabin, si estuviera satisfecho con la confianza de que su respuesta es correcta en lugar de una prueba de que sí lo es. Si un número supera las 15 pruebas, entonces es compuesto con una probabilidad inferior a 1 . en mil millones)

Answer 7

un fácil de implementar el algoritmo que le llevará mucho más lejos que la división de prueba es Pollard Rho

Aquí es una aplicación Java, que debe ser fácil de adaptar a C#: http://www.cs.princeton.edu/introcs/78crypto/PollardRho.java.html

Answer 8

https://codility.com/demo/results/demoAAW2WH-MGF/

public int solution(int n) { 
     var counter = 0;   
     if (n == 1) return 1; 
     counter = 2; //1 and itself  
     int sqrtPoint = (Int32)(Math.Truncate(Math.Sqrt(n))); 
     for (int i = 2; i <= sqrtPoint; i++) 
     { 
     if (n % i == 0) 
     { 
      counter += 2; // We found a pair of factors.   
     }  
     } 
     // Check if our number is an exact square. 
     if (sqrtPoint * sqrtPoint == n) 
     { 
     counter -=1; 
     } 

     return counter; 
    }