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

Ответ 1

псевдокод:

• Петля от 1 до квадратного корня из числа, вызовите индекс "i".
• если номер mod я равен 0, добавьте я и число /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> заключается в том, что он может быть отсортирован перед возвратом, если требуется. Опять же, вы можете получить отсортированный счетчик с гибридным подходом, который даст первый коэффициент и сохранит второй в каждой итерации цикла, а затем даст каждое значение, которое было сохранено в обратном порядке.

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

Ответ 2

Оператор % (остаток) - это тот, который можно использовать здесь. Если x % y == 0, то x делится на y. (Предполагая 0 < y <= x)

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

Ответ 3

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

Благодаря Мерлину, я получил причину квадрата как "макс" ниже исправленного образца. хотя ответ от 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;
                }
            }
        }
    }

Ответ 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 этот алгоритм может занять много времени.

Ответ 5

Другой стиль 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;
            }


        }

Ответ 6

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

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

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

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

Ответ 7

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

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

EDIT. Как отметил Краанг Прайм, эта функция не может превышать предел целого числа и является (по общему признанию) не самым эффективным способом решения этой проблемы.

Ответ 8

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

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

Ответ 9

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

Ответ 10

Решение Linq:

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