Перебір дільників

Перебір дільників – алгоритм розкладання числа на прості множники шляхом повного перебору всіх можливих дільників.

Опис алгоритму

Один з найбільш простих та очевидних алгоритмів факторизації, який Один из самых простых и очевидных алгоритмов факторизации, полягає в тому, щоб послідовно ділити число 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();
}