Encontrando de manera eficiente todos los divisores de un número

Question

Así que simplemente quiero encontrar todos los divisores de un número dado (excepto el número en sí). Actualmente, tengo esto:

public static List<int> proper_divisors(int x) 
{ 
    List<int> toreturn = new List<int>(); 
    toreturn.Add(1); 
    int i = 0; 
    int j=1; 
    int z = 0; 
    while (primes.ElementAt(i) < Math.Sqrt(x)) 
    { 
     if (x % primes.ElementAt(i) == 0) 
     { 
      toreturn.Add(primes.ElementAt(i)); 
      toreturn.Add(x/primes.ElementAt(i)); 
      j = 2; 
      z = (int)Math.Pow(primes.ElementAt(i), 2); 
      while (z < x) 
      { 
       if (x % z == 0) 
       { 
        toreturn.Add(z); 
        toreturn.Add(x/z); 
        j++; 
        z = (int)Math.Pow(primes.ElementAt(i), j); 
       } 
       else 
       { 
        z = x; 
       } 
      } 
     } 
     i++; 
    } 
    toreturn = toreturn.Distinct().ToList<int>(); 
    return toreturn; 
} 

donde los números primos es una lista de los números primos (asuma que es correcto, y es lo suficientemente grande). El algoritmo funciona en el sentido de que encuentra todos los factores primos, pero no todos los factores (es decir, dado 34534, devuelve {1,2,17267,31,1114} pero falla {62, 557} ya que 62 es una combinación , y por lo tanto pierde 557 también.

tengo también intentó conseguir justo los factores primos de un número, pero no sé cómo convertir esto en una lista de todas las combinaciones correctas.

El código para que el algoritmo es el siguiente:

public static List<int> prime_factors(int x) 
{ 
    List<int> toreturn = new List<int>(); 
    int i = 0; 
    while (primes.ElementAt(i) <= x) 
    { 
     if (x % primes.ElementAt(i) == 0) 
     { 
      toreturn.Add(primes.ElementAt(i)); 
      x = x/primes.ElementAt(i); 
     } 
     else 
     { 
      i++; 
     } 
    } 
    return toreturn; 
} 

¿Alguna idea sobre cómo solucionar el primero de ellos, o cómo crear la lista de combinaciones de la segunda d uno (lo preferiría porque sería más rápido)?

Answer 1

Ya que usted tiene una lista de los factores primos, lo que quiere hacer es calcular el powerset de esa lista.

Ahora, un problema es que puede tener duplicados en la lista (por ejemplo, los factores primos de 20 = 2 * 2 * 5), pero los conjuntos no permiten duplicados. Por lo tanto, podemos hacer que cada elemento de la lista sea único al proyectarlo a una estructura de la forma {x, y} donde x es el primo ey es el índice del primo en la lista.

var all_primes = primes.Select((x, y) => new { x, y }).ToList(); 

Ahora, all_primes es una lista de la forma {x, y}, donde x es el primer e y es el índice en la lista.

A continuación, calcular el conjunto de alimentación (definición de GetPowerSet a continuación):

var power_set_primes = GetPowerSet(all_primes); 

Por lo tanto, power_set_primes es un IEnumerable<IEnumerable<T>> donde T es el tipo anónimo {x, y}, donde x e y son de tipo int.

A continuación, se calcula el producto de la cada elemento en el poder establecido

foreach (var p in power_set_primes) 
{ 
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y); 
    factors.Add(factor); 
} 

Poniendo todo junto:

var all_primes = primes.Select((x, y) => new { x, y }).ToList(); //assuming that primes contains duplicates. 
var power_set_primes = GetPowerSet(all_primes); 
var factors = new HashSet<int>(); 

foreach (var p in power_set_primes) 
{ 
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y); 
    factors.Add(factor); 
} 

De http://rosettacode.org/wiki/Power_Set para las implementaciones de powerset.

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

Answer 2

Ha habido una pregunta similar before, que tiene una interesante solución usando IEnumerable. Si quieres todos los divisores y no los factores, y suponiendo que estás usando al menos C# 3.0 podría utilizar algo como esto:

static IEnumerable<int> GetDivisors(int n) 
{ 
    return from a in Enumerable.Range(2, n/2) 
      where n % a == 0 
      select a;      
} 

y luego usarlo como esto:

foreach(var divisor in GetDivisors(10)) 
    Console.WriteLine(divisor); 

o, si desea una lista, simplemente:

List<int> divisors = GetDivisors(10).ToList();