Лучший способ найти все факторы данного числа

Question

Все числа, которые делятся поровну на x.

Я положил в 4, он возвращает: 4, 2, 1

редактировать: я знаю, это звучит домашнее задание. Я пишу небольшое приложение, чтобы заполнить некоторые таблицы продуктов полу случайными тестовыми данными. Двумя свойствами являются ItemMaximum и Item Multiplier. Мне нужно убедиться, что множитель не создаст нелогичной ситуации, когда покупка еще 1 предмета поставит ордер выше максимально допустимого. Таким образом, факторы предоставят список допустимых значений для моих тестовых данных.

редактировать ++: Это то, с чем я пошел после помощи всех. Еще раз спасибо!

edit #: я написал 3 разные версии, чтобы увидеть, какая мне понравилась больше, и проверил их по факторингу малых и очень больших чисел. Я вставлю результаты.

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

В тиках. При факторинге число 20, каждое 5 раз:

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

При разложении числа 20000 по 5 раз:

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

Answer 1

псевдокод:

• Цикл от 1 до квадратного корня числа, вызовите индекс "i".
• если число mod i равно 0, добавьте i и число / i в список факторов.

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

Как упоминал Джон Скит, вы также можете реализовать это как IEnumerable<int> - используйте yield вместо добавления в список. Преимущество List<int> заключается в том, что при необходимости его можно отсортировать перед возвратом. С другой стороны, вы могли бы получить отсортированный перечислитель с гибридным подходом, получая первый фактор и сохраняя второй в каждой итерации цикла, а затем получая каждое значение, которое было сохранено в обратном порядке.

Вы также захотите сделать что-нибудь для обработки случая, когда в функцию передано отрицательное число.

Answer 2

Оператор % (остаток) используется здесь. Если x % y == 0, то x делится на y. (Предполагая 0 < y <= x)

Я бы лично реализовал это как метод, возвращающий IEnumerable<int> с использованием блока итератора.

Answer 3

Очень поздно, но принятый ответ (некоторое время назад) не дал правильных результатов.

Благодаря Мерлин, я получил причину для квадрата как 'max' ниже исправленного образца. Хотя ответ от Echostorm кажется более полным.

    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 4

Как методы расширения:

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

Вот пример использования:

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

Обратите внимание, что я оптимизировал для ясности, а не для производительности. Для больших значений i этот алгоритм может занять много времени.

Answer 5

Я сделал это ленивым образом. Я не знаю много, но мне сказали, что простота иногда подразумевает элегантность. Это один из возможных способов сделать это:

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

РЕДАКТИРОВАТЬ : Как отметил Краанг Прайм, эта функция не может превышать предел целого числа и является (по общему признанию) не самым эффективным способом решения этой проблемы.

Answer 6

Другой стиль LINQ и связывание, чтобы сохранить сложность 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 7

Вот и снова, считая только до квадратного корня, как уже упоминалось. Я полагаю, что людей привлекает эта идея, если вы надеетесь улучшить производительность. Я предпочел бы сначала написать элегантный код, а потом оптимизировать производительность после тестирования моего программного обеспечения.

Тем не менее, для справки, вот оно:

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

Мало того, что результат значительно менее читабелен, но и факторы выходят из строя и в этом случае.

Answer 8

И еще одно решение. Не уверен, что у него есть какие-либо преимущества, кроме читабельности ..:

List<int> GetFactors(int n)
{
    var f = new List<int>() { 1 };  // adding trivial factor, optional
    int m = n;
    int i = 2;
    while (m > 1)
    {
        if (m % i == 0)
        {
            f.Add(i);
            m /= i;
        }
        else i++;
    }
    // f.Add(n);   // adding trivial factor, optional
    return f;
}

Answer 9

Если вы используете double, работает следующее: используйте цикл for с итерацией от 1 до числа, которое вы хотите вычислить. В каждой итерации делим число, которое будет учтено i. Если (число / i)% 1 == 0, то i является фактором, как и частное от числа / i. Поместите один или оба из них в список, и у вас есть все факторы.

Answer 10

Разве не имеет смысла начинать с 2 и двигаться к верхнему предельному значению, которое непрерывно пересчитывается на основе только что проверенного числа? См. N / i (где N - число, для которого вы пытаетесь найти коэффициент, а i - текущее число для проверки ...). В идеале вместо мода вы должны использовать функцию деления, которая также возвращает N / i как и любой другой остаток. Таким образом, вы выполняете одну операцию деления, чтобы воссоздать как верхнюю границу, так и остаток, который вы проверите для четного деления.

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