c# - numeros - La mejor forma de encontrar todos los factores de un número determinado

factores primos

Question

Todos los números que se dividen equitativamente en x.

Puse 4 que regresa: 4, 2, 1

editar: Sé que suena muy casero. 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.

editar ++: Esto es lo que hice después de toda la ayuda de todos. ¡Gracias de nuevo!

edición #: escribí 3 versiones diferentes para ver cuál me gustaba más y las probé 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;
        }
    }
}

En tics. Al factorizar el número 20, 5 veces cada uno:

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

Al factorizar el número 20000, 5 veces cada uno:

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

Answer 1

¿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 acabas 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 2

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.

Aún así, como 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 solo el resultado es considerablemente menos legible, sino que los factores también se vuelven anormales.

Answer 3

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 mayor claridad, no para el rendimiento. Para valores grandes de i este algoritmo puede llevar mucho tiempo.

Answer 4

El operador % (remainder) es el que debe usarse aquí. Si x % y == 0 entonces x es divisible por y . (Suponiendo 0 < y <= x )

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

Answer 5

Lo hice de 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 señaló Kraang Prime, esta función no puede exceder el límite de un número entero y (por cierto) no es la forma más eficiente de manejar este problema.

Answer 6

Muy tarde, pero la respuesta aceptada (hace un tiempo) no dio los resultados correctos.

Gracias a Merlyn, ahora obtuve el motivo del cuadrado como un "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 7

Otro estilo LINQ y vincular para mantener la complejidad O (sqrt (n))

        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

Si usa dobles, lo siguiente funciona: use un bucle for para iterar desde 1 hasta el número que desea 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 9

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 10

pseudocódigo:

• Pasa de 1 a la raíz cuadrada del número, llama 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 mencionó Jon Skeet, también podría implementar esto como un IEnumerable<int> : use el yield lugar de agregarlo 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 donde un número negativo pasó a la función.