La mejor manera de encontrar todos los factores de un número determinado

Question

Todos los números que se dividen de manera uniforme en x.

puse en 4 vuelve: 4, 2, 1

edición: Sé que suena homeworky. Estoy escribiendo una pequeña aplicación para completar algunas tablas de productos con datos de prueba semialeatorios. Dos de las propiedades son ItemMaximum y Item Multiplier. Necesito asegurarme de que el multiplicador no cree una situación ilógica donde comprar 1 artículo más pondría la orden por encima del máximo permitido. Por lo tanto, los factores darán una lista de valores válidos para mis datos de prueba.

edición ++: Esto es lo que fui con toda la ayuda de todos. ¡Gracias de nuevo!

Editar #: Escribí 3 versiones diferentes para ver cuál me gustaba más y las comprueve contra factorizar números pequeños y números muy grandes. Pegaré los resultados.

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

private IEnumerable<int> GetFactors3(int x) 
{    
    for (int factor = 1; factor * factor <= x; factor++) 
    { 
     if (x % factor == 0) 
     { 
      yield return factor; 
      if (factor * factor != x) 
       yield return x/factor; 
     } 
    } 
} 

private IEnumerable<int> GetFactors1(int x) 
{ 
    int max = (int)Math.Ceiling(Math.Sqrt(x)); 
    for (int factor = 1; factor < max; factor++) 
    { 
     if(x % factor == 0) 
     { 
      yield return factor; 
      if(factor != max) 
       yield return x/factor; 
     } 
    } 
} 

In ticks. cuando se toma el número 20, 5 veces cada uno:

• GetFactors1-5,445,881
• GetFactors2-4,308,234
• GetFactors3-2,913,659

cuando se toma el número 20000, 5 veces cada uno:

• GetFactors1-5,644,457
• GetFactors2-12,117,938
• GetFactors3-3,108,182

Answer 1

pseudocódigo:

• bucle de 1 a la raíz cuadrada del número, llame al índice "i".
• si el número mod i es 0, agregue i y number/i a la lista de factores.

realocode:

public List<int> Factor(int number) { 
    List<int> factors = new List<int>(); 
    int max = (int)Math.Sqrt(number); //round down 
    for(int factor = 1; factor <= max; ++factor) { //test from 1 to the square root, or the int below it, inclusive. 
     if(number % factor == 0) { 
      factors.Add(factor); 
      if(factor != number/factor) { // Don't add the square root twice! Thanks Jon 
       factors.Add(number/factor); 
      } 
     } 
    } 
    return factors; 
} 

Como se mencionó Jon Skeet, podría implementar esto como una IEnumerable<int> así - yield utilizar en lugar de añadir a una lista. La ventaja con List<int> es que se puede ordenar antes de devolver si es necesario. Por otra parte, podría obtener un enumerador ordenado con un enfoque híbrido, obteniendo el primer factor y almacenando el segundo en cada iteración del ciclo, y luego arrojando cada valor almacenado en orden inverso.

También querrá hacer algo para manejar el caso en el que un número negativo pasó a la función.

Answer 2

El operador % (resto) es el que debe utilizarse aquí. Si x % y == 0, entonces x es divisible por y. (Asumiendo 0 < y <= x)

Personalmente implementaría esto como un método que devuelve un IEnumerable<int> usando un bloque iterador.

Answer 3

solución LINQ:

IEnumerable<int> GetFactors(int n) 
{ 
    Debug.Assert(n >= 1); 
    return from i in Enumerable.Range(1, n) 
     where n % i == 0 
     select i; 
} 

Answer 4

Como métodos de extensión:

public static bool Divides(this int potentialFactor, int i) 
    { 
     return i % potentialFactor == 0; 
    } 

    public static IEnumerable<int> Factors(this int i) 
    { 
     return from potentialFactor in Enumerable.Range(1, i) 
       where potentialFactor.Divides(i) 
       select potentialFactor; 
    } 

Aquí hay un ejemplo de uso:

 foreach (int i in 4.Factors()) 
     { 
      Console.WriteLine(i); 
     } 

Tenga en cuenta que he optimizado para una mayor claridad, no para el rendimiento. Para valores grandes de i, este algoritmo puede llevar mucho tiempo.

Answer 5

Aquí está de nuevo, solo contando a la raíz cuadrada, como otros mencionaron. Supongo que la gente se siente atraída por esa idea si espera mejorar el rendimiento. Prefiero escribir un código elegante primero, y optimizar el rendimiento más adelante, después de probar mi software.

Sin embargo, para referencia, aquí está:

public static bool Divides(this int potentialFactor, int i) 
    { 
     return i % potentialFactor == 0; 
    } 

    public static IEnumerable<int> Factors(this int i) 
    { 
     foreach (int result in from potentialFactor in Enumerable.Range(1, (int)Math.Sqrt(i)) 
           where potentialFactor.Divides(i) 
           select potentialFactor) 
     { 
      yield return result; 
      if (i/result != result) 
      { 
       yield return i/result; 
      } 
     } 
    } 

No sólo es el resultado considerablemente menos legible, pero los factores que vienen fuera de esta manera, también.

Answer 6

¿No tendría sentido también comenzar en 2 y dirigirse hacia un valor límite superior que continuamente se recalcula según el número que acaba de marcar? Vea N/i (donde N es el número que está tratando de encontrar el factor de y i es el número actual para verificar ...) Idealmente, en lugar de mod, usaría una función de división que también devuelve N/i como cualquier resto que pueda tener. De esa forma estás realizando una operación dividida para recrear tu límite superior, así como el resto verificará la división par.

Math.DivRem http://msdn.microsoft.com/en-us/library/wwc1t3y1.aspx

Answer 7

Otro estilo de LINQ y atar para mantener la junta (sqrt (n)) la complejidad

 static IEnumerable<int> GetFactors(int n) 
     { 
      Debug.Assert(n >= 1); 
      var pairList = from i in Enumerable.Range(1, (int)(Math.Round(Math.Sqrt(n) + 1))) 
        where n % i == 0 
        select new { A = i, B = n/i }; 

      foreach(var pair in pairList) 
      { 
       yield return pair.A; 
       yield return pair.B; 
      } 


     } 

Answer 8

muy tarde, pero la respuesta aceptada (un tiempo) no lo hicieron no dar los resultados correctos.

Gracias a Merlyn, ahora obtuve el motivo del cuadrado como 'máximo' debajo de la muestra corregida. aunque la respuesta de Echostorm parece más completa.

public static IEnumerable<uint> getFactors(uint x) 
    { 
     for (uint i = 1; i*i <= x; i++) 
     { 
      if (0 == (x % i)) 
      { 
       yield return i; 
       if (i != (x/i)) 
       { 
        yield return x/i; 
       } 
      } 
     } 
    } 

Answer 9

Si usa dobles, las siguientes opciones funcionan: utilice un bucle for para iterar desde 1 hasta el número que desee factorizar. En cada iteración, divida el número que será factorizado por i. Si (número/i)% 1 == 0, entonces yo es un factor, como lo es el cociente de número/i. Coloque uno o ambos en una lista, y usted tiene todos los factores.

Answer 10

Lo hice de la manera perezosa. No sé mucho, pero me han dicho que la simplicidad a veces puede implicar elegancia. Esta es una forma posible de hacerlo:

public static IEnumerable<int> GetDivisors(int number) 
    { 
     var searched = Enumerable.Range(1, number) 
      .Where((x) => number % x == 0) 
      .Select(x => number/x); 

     foreach (var s in searched)   
      yield return s; 
    } 

EDITAR: Como Kraang Primer señaló, esta función no puede exceder el límite de un número entero y es (la verdad) no es la forma más eficiente de manejar este problema.