La forma más eficiente para obtener todos los divisores de un número

Question

Duplicar posibles:
Efficiently finding all divisors of a number

Esto es mucho más que una cuestión de eficiencia de un genérico "encontrar una manera de hacerlo ", pero después de obtener algunos resultados extraños, quiero ver si alguien me puede decir por qué la última manera es tan ineficiente:

manera 1: fuerza bruta, sin optimización

public static List<int> proper_divisors(int x) 
    { 
     List<int> toreturn = new List<int>(); 
     for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++) 
     { 
      if (x % i == 0) 
      { 
       toreturn.Add(i); 
       toreturn.Add(x/i); 
      } 
     } 
     if (toreturn.ElementAt(toreturn.Count()/2) == toreturn.ElementAt(toreturn.Count()/2 - 1)) 
     { 
      toreturn.Remove(toreturn.ElementAt(toreturn.Count()/2)); 
     } 

     return toreturn; 
    } 

manera 2: igual que antes, pero esta vez, comprobar si su primer primero (como aquellos casos ocupan la mayor parte del tiempo, el uso de Miller-Rabin para la comprobación primer)

 public static List<int> proper_divisors(int x) 
    { 
     List<int> toreturn = new List<int>(); 
     if (!isprime(x)) 
     { 
      for (int i = 1; i <= Math.Floor(Math.Sqrt(x)); i++) 
      { 
       if (x % i == 0) 
       { 
        toreturn.Add(i); 
        toreturn.Add(x/i); 
       } 
      } 
      if (toreturn.ElementAt(toreturn.Count()/2) == toreturn.ElementAt(toreturn.Count()/2 - 1)) 
      { 
       toreturn.Remove(toreturn.ElementAt(toreturn.Count()/2)); 
      } 
     } 
     else 
     { 
      toreturn.Add(1); 
      toreturn.Add(x); 

     } 
     return toreturn; 
    } 

lo que se pensaba sería la forma más rápida de lejos, era el camino 3, porque reducía el número con el que estaba trabajando cada vez que encontraba un factor primo, y solo probaba los primos (estos fueron generados por un tamiz en tiempo de ejecución, tarda unos 34 ms en obtener todos los primos menos de un millón) lo último que tuvo que hacer esta forma fue tomar los factores primos y sus poderes, y hacer una lista de todos los factores.

manera 3:

   public static HashSet<int> prime_factors(int x) 
    { 
     if (!isprime(x)) 
     { 
      List<int> toreturn = new List<int>(); 
      int i = 0; 
      while (primes[i] <= x) 
      { 
       if (x % primes[i] == 0) 
       { 
        toreturn.Add(primes[i]); 
        x = x/primes[i]; 
       } 
       else 
       { 
        i++; 
       } 
      } 
      var power_set_primes = GetPowerSet(toreturn); 
      var factors = new HashSet<int>(); 
      foreach (var p in power_set_primes) 
      { 
       var factor = p.Select(z => z).Aggregate(1, (z, y) => z * y); 
       factors.Add(factor); 
      } 
      return factors; 
     } 
     else 
     { 
      HashSet<int> toreturn = new HashSet<int>(); 
      toreturn.Add(1); 
      toreturn.Add(x); 
      return toreturn; 
     } 
     public static IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list) 
    { 
     return from m in Enumerable.Range(0, 1 << list.Count) 
       select 
        from i in Enumerable.Range(0, list.Count) 
        where (m & (1 << i)) != 0 
        select list[i]; 
    } 

tiempo que tomó para factorizar el primer millón de números: modo 1: 7223 ms manera 2: 8985 ms (comprobación primer no vale la pena para los números pequeños que supongo) modo 3: 49423 ms

por lo que mi pregunta es doble: 1) ¿por qué es la forma 3 tan lenta ??? 2) ¿hay algo que pueda hacerlo más rápido? como un lado, primos se calculó como una lista, luego se convirtió en una matriz, ya que pensé que sería más rápido de esa manera. ¿mal movimiento?

Answer 1

Este es el dominio del problema de la factorización de enteros. Hay una serie de algoritmos bien conocidos aquí:

http://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms

sugiero que elija el mejor partido + perfil.

---

mi comentario inicial:

perfil perfil perfil. Además, no use enumeradores ni LINQ si le interesa la eficiencia. Escríbalo en C y usa P/Invoke. En general, no pregunte si puede medirlo