Перебор делителей

Перебор делителей – алгоритм разложения числа на простые множители путём полного перебора всех возможных потенциальных делителей.

Описание алгоритма

Один из самых простых и очевидных алгоритмов факторизации, заключающийся в том, чтобы последовательно делить факторизуемое число n на натуральные числа от 1 до n.

Реализация алгоритма

static List<uint> TrialDivision(uint n)
{
    var divides = new List<uint>();
    var div = 2u;
    while (n > 1)
    {
        if (n % div == 0)
        {
            divides.Add(div);
            n /= div;
        }
        else
        {
            div++;
        }
    }

    return divides;
}

Скорость вычислений можно повысить, поскольку n достаточно делить на простые числа квадрат которых меньше n.

static List<uint> TrialDivision(uint n)
{
    var divides = new List<uint>();
    var div = 2u;
    while (n % div == 0)
    {
        divides.Add(div);
        n /= div;
    }

    div = 3;

    while (Math.Pow(div, 2) <= n)
    {
        if (n % div == 0)
        {
            divides.Add(div);
            n /= div;
        }
        else
        {
            div += 2;
        }
    }

    if (n > 1)
    {
        divides.Add(n);
    }

    return divides;
}

Программа для разложения числа на множители методом пребора делителей

static void Main(string[] args)
{
    Console.Write("n = ");
    var n = Convert.ToUInt32(Console.ReadLine());
    Console.WriteLine("{0} = {1}", string.Join(" * ", TrialDivision(n)), n);
    Console.ReadLine();
}