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

"Я хочу, чтобы меня услышали в России. Абсолютно все. Тысячи жертв, сотни пленных, которые просто не могут понять ради чего их отправили в Украину.
Отправили в Украину умирать. Убивать других. Чем скорее вы скажете своей власти, что войну нужно немедленно остановить – тем больше ваших людей останутся живыми.
Мы видим, что действительно есть выступления ваших граждан против войны. И мы знаем, что многие в России сейчас просто шокированы подлостью и жестокостью власти. И это очень правильная реакция. Я благодарю вас за эту реакцию! Спасибо Леониду Парфёнову, Дмитрию Муратову, Юрию Дудю, Лие Ахеджаковой, Валерию Меладзе – ну, и тысячам. Тысячам достойных других россиян, чья совесть звучит – звучит громко.
Просто остановите тех, кто лжет вам. Лжет нам. Лжет всему миру.
Нужно закончить эту войну. Мы можем жить в мире. В мире глобальном. В мире человечества".

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

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

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

В классе программы, возле метода Main, должен располагаться один из выше приведенных методов факторизации.

Смотрите также: