Разложение числа на простые множители

Что такое простые множители?

Простое число — это такое число, которое делится нацело только на единицу и на само себя. Например, число 7 простое, потому что его можно разделить только на 1 и 7. А число 8 — не простое, потому что у него много делителей: 1, 2, 4 и 8.

Если значение можно получить умножением одних чисел на другие, не считая единицы и самого числа, то такие числа называют множителями числа. В нашем примере у числа 8 множители 2 и 4. У числа 18 множителей больше — 2, 3, 6 и 9:

2 × 9 = 18

3 × 6 = 18

6 × 3 = 18

9 × 2 = 18

В нашей задаче нужно найти все простые множители числа. Это значит, что среди всех множителей нужно выбрать только простые числа. Разберём множители числа 18:

2 — простое, подходит для ответа

3 — простое, тоже подходит для ответа

6 — составное, потому что 6 = 2 × 3

9 — составное, потому что 9 = 3 × 3

Значит, если мы введём число 18, программа должна выдать в ответ числа 2 и 3.

Логика решения будет такой:

Делаем одну большую функцию, внутри которой и будут происходить все вычисления. В конце работы мы скормим этой функции искомое число. 

Внутри этой функции делаем вспомогательную функцию — она будет проверять, простое число ей передали на проверку или не простое. 

После этого перебираем все числа от 2 до введённого числа и смотрим, делится введённое число на это или нет. Если делится, то проверяем, простое оно или нет. Если простое — добавляем в массив с решением.

Наконец вызываем нашу большую функцию, передаём ей число на проверку и смотрим результат в консоли.

Теперь читайте комментарии в итоговом коде:

Почему вы не используете квадратный корень, как все?

Почти в каждом решении из интернета есть один лайфхак: цикл перебирает множители не до самого числа, а меньше: до квадратного корня этого числа. Например, если бы мы искали простые множители числа 64, то цикл прошёл бы до числа 8.

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

Математическое объяснение приёма с квадратным корнем звучит так: если число можно разложить на два множителя, то оба эти множителя одновременно не могут быть больше квадратного корня этого числа. По-другому — один из множителей точно не будет больше квадратного корня. Соответственно, другой множитель может быть больше. 

Проблема в том, что мы не находим множители попарно. Мы находим их один за другим. Наш алгоритм не помнит, какие множители он уже нашёл.

Например, возьмём число 77. Оно состоит из двух простых множителей: 7 и 11. Квадратный корень из 77 равен 8,77. В паре множителей 7 и 11 только один из них больше 8,77, значит, условие выполняется: оба множителя одновременно не больше квадратного корня нашего числа. 

Теперь, если бы мы искали множители вручную, мы бы действительно перебирали все множители до 8,77. Мы бы нашли множитель 7, разделили бы 77 на 7 и получили бы 11. Так мы бы получили два множителя: 7 и 11. Это простые числа, нас этот результат удовлетворил бы. 

Но наш алгоритм ищет множители не парами, а по одному. Если бы мы перебирали множители до 8,77, то мы бы нашли только множитель 7. Множитель 11 мы бы не нашли, ведь алгоритм остановился бы.

Поэтому конкретно с нашим алгоритм трюк с квадратным корнем не пройдёт. Но можно использовать другие оптимизации.

На подумать: сейчас в алгоритме мы перебираем все числа от двойки до введённого числа, но есть способ сократить количество переборов. Попробуйте найти его самостоятельно.

Текст:

Михаил Полянин

Редактура:

Максим Ильяхов

Художник:

Даня Берковский

Корректор:

Ирина Михеева

Вёрстка:

Мария Дронова

Соцсети:

Олег Вешкурцев

Простые и составные числа

Определение 1

Простыми числами являются целые числа, которые больше единицы и имеют только $2$ положительных делителя (само себя и $1$).

Определение 2

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

Замечание 1

Отметим, что число 1 – ни простое, ни составное. У единицы лишь один положительный делитель – это само число $1$.

Т.к. целыми положительными числами являются натуральные числа, а у единицы только один положительный делитель, то можно сформулировать следующие определения простых и составных чисел.

Определение 3

Простыми числами называются натуральные числа, у которых только $2$ положительных делителя.

Определение 4

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

Пример 1

Примером простых чисел являются числа $2$, $7$, $11$, $17$, $19$, $29$, $131$, $523$. Для данных чисел невозможно подобрать какой-нибудь положительный делитель, который отличается от единицы и самого этого числа.

Пример 2

Примером составных чисел являются числа $8$, $51$, $100$. У числа $8$ кроме положительных делителей $1$ и $8$ есть делители $2$ и $4$, т.к. $8=2\cdot 4$, поэтому $8$ является составным числом.

У числа $51$ есть положительные делители $1$, $3$, $17$ и $51$. Число $100$ имеет положительные делители $1, 2, 4, 5, 10, 20, 25, 50$ и $100$.

Любое составное число может быть разложено на $2$ множителя, больших $1$.

Пример 3

Например, $9=3\cdot 3$, $36=2\cdot 2\cdot 3\cdot 3$, $66=2\cdot 3\cdot 11$ и т.д.

Замечание 2

Простое число на $2$ множителя, больших $1$, разложить нельзя.

Замечание 3

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

Признаки делимости чисел

Признаки делимости чисел используются для того, чтобы ускорить процесс деления чисел. Существует множество признаков делимости и других интересных алгоритмов, значительно ускоряющих решение и освобождающих от излишней волокиты. Рассмотрим наиболее популярные из них.

Признак делимости на 10

Любое число, которое оканчивается нулем, делится без остатка на 10. Чтобы получить частное, достаточно отбросить цифру 0 в делимом.

Например, 380 : 10 = 38. Мы просто отбросили последний ноль в числе 380.

В случае, если мы имеем выражение такого вида 385 : 10, то получится 38 и 5 в остатке, поскольку 380 : 10 = 38, а пятерка это остаток, который не разделился.

Таким образом, если число оканчивается цифрой 0, то оно делится без остатка на 10. Если же оно оканчивается другой цифрой, то оно не делится без остатка на 10. Остаток в этом случае равен последней цифре числа. Действительно, в примере 385 : 10 = 38 (5 в остатке), остаток равен последней цифре в числе 385, то есть пятерке.

Признак делимости на 5 и на 2

Любое число, которое оканчивается нулем, делится без остатка и на 5, и на 2.

Примеры:

10 : 5 = 2

100 : 5 = 20

100 : 2 = 50

Признак делимости на 5

Если число оканчивается цифрой 0 или 5, то оно делится без остатка на 5.

Примеры:

355 : 5 = 71

200 : 5 = 40

475 : 5 = 95

Признак делимости на 3

Число делится на 3, если сумма цифр этого числа делится на 3. Например, рассмотрим число 27, сумма его цифр 2 + 7 = 9. Девять, как мы знаем делится на 3, значит и 27 делится на 3:

27 : 3 = 9

Признак делимости на 9

Число делится на 9, если сумма его цифр делится на 9. Например, рассмотрим число 18. Сумма его цифр 1 + 8 = 9. Девять делится на девять, значит и 18 делится на 9

18 : 9 = 2

Рассмотрим число 846. Сумма его цифр 8 + 4 + 6 = 18.  Восемнадцать делится на девять, значит и 846 делится на 9:

Метод Эратосфена

Метод Эратосфена — это алгоритм для нахождения всех простых чисел до заданного числа. Он основан на следующей идее: если число является простым, то все его кратные числа будут составными. Таким образом, можно удалить все кратные числа, начиная с 2 и до заданного числа, и оставить только простые числа в итоге.

Шаги выполнения метода Эратосфена:

1. Создать список чисел от 2 до заданного числа.
2. Взять первое число из списка (2) и отметить его как простое.
3. Удалить из списка все его кратные числа.
4. Взять следующее непомеченное число из списка и повторить шаги 3-4.
5. Повторять шаги 3-4, пока остаются непомеченные числа в списке.

В итоге, после применения метода Эратосфена, в списке останутся только простые числа до заданного числа.

Пример	Шаг 1	Шаг 2	Шаг 3	Шаг 4	Шаг 5
Исходный список чисел от 2 до 10	2, 3, 4, 5, 6, 7, 8, 9, 10	2, 3, 4, 5, 6, 7, 8, 9, 10	2, 3, 5, 7, 9	2, 3, 5, 7	2, 3, 5, 7

В результате применения метода Эратосфена для списка чисел от 2 до 10, останутся только простые числа: 2, 3, 5, 7.

Метод Эратосфена является эффективным способом нахождения простых чисел и используется в различных задачах, связанных с числами и факторизацией. Он широко применяется в математике, информатике и криптографии.

Классический алгоритм Евклида

Этот вид алгоритма Евклида является самым простым, он был придуман более 1300 лет назад. С появлением электронно-вычислительных машин расширились возможности по применению алгоритма Евклида, возникли новые более эффективные его реализации.

Алгоритм состоит из определенного количества шагов, количество которых зависит от размера входных данных.

Сложность алгоритма выражается функцией O(h2), где h – это количество десятичных цифр в наименьшем числе, наибольший делитель которых ищется алгоритмом.

Реализация на Python

Существует несколько реализаций классического алгоритма Евклида, которые основаны на использовании различных операторов и возможностей языка Python (остаток от деления, вычитание, рекурсия). Эти реализации отличаются незначительно, сильные различия в эффективности наблюдаются только при специфических входных данных.

Реализация с помощью остатка от деления

Идея такой реализации достаточна проста, алгоритм уменьшает числа до тех пор, пока одно из них не станет равно нулю, а другое искомому делителю. Для этого используется цикл , в котором большее число делится на меньшее и становится равным остатку от деления. Таким образом, функция вернёт наибольший общий делитель (НОД) её двух аргументов.

Код алгоритма Евклида на Python:

def gcd_rem_division(num1, num2):
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 %= num2
        else:
            num2 %= num1
    return num1 or num2

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

В каждой новой итерации большее число становится меньшим и наоборот. Возьмём числа 168 и 105 и распишем работу программы вручную:

• 1 итерация:
  168 % 105 = 63
  105
• 2 итерация:
  63
  105 % 63 = 42
• 3 итерация:
  63 % 42 = 21
  42
• 4 итерация:
  42 % 21 = 0
  21

После 4 итерации алгоритм завершает свою работу, так как одно из чисел равно нулю, второе же число равно наибольшему общему делителю, в нашем случае это 21. Проверим работу программы:

a = gcd_rem_division(168, 105)
print(a) # Выведет 21

Реализация с помощью вычитания

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

Код вычисления НОД на Python:

def gcd_subtraction(num1, num2):
    while num1 != 0 and num2 != 0:
        if num1 >= num2:
            num1 -= num2
        else:
            num2 -= num1
    return num1 or num2

Также распишем работу программы с числами 168 и 105:

• 1 итерация:
  168 — 105 = 63
  105
• 2 итерация:
  63
  105 — 63 = 42
• 3 итерация:
  63 — 42 = 21
  42
• 4 итерация:
  21
  42 — 21 = 21
• 5 итерация:
  21 — 21 = 0
  21

Видно, что до 4 итерации результаты работы обоих версий алгоритма полностью совпадают. Отличия начинаются, когда в 4 итерации вместо 0 и 21, получается числа 21 и 21, из-за чего в алгоритме с вычитанием добавляется дополнительная итерация, но это не значит, что он работает менее эффективнее.

Проверка работы программы:

a = gcd_subtraction(168, 105)
print(a) # Выведет 21

Реализация с помощью рекурсии

Суть алгоритма схожа с реализацией через остаток от деления, однако вместо цикла используется рекурсия.

Код программы на Python нахождения НОД с помощью рекурсии:

def gcd_recursion(num1, num2):
    if num1 == 0:
        return num2
    return gcd_recursion(num2 % num1, num1)

Первое, что стоит заметить, на ноль проверяется только

Важно понять, что числа постоянно меняются местами. В качестве первого числа в рекурсивный вызов функции передаётся , вспомним 4 итерацию в алгоритме через остаток от деления:

4 итерация:
42 % 21 = 0 — num1
21 — num2

То есть рекурсивный алгоритм проверит число на ноль, получит True и вернёт значение , которое и будет являться наибольшим общим делителем.

Особенности алгоритма: простые числа

Если два переданных числа не имеют общих делителей, то алгоритм возвращает единицу. Действительно, ведь каждое число делится на единицу. Например, числа 35 и 18 не имеют общих делителей:

• 35 = 5 * 7 * 1
• 18 = 2 * 9 * 1 = 3 * 6 * 1

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

Если алгоритм получает на вход одно простое число, это не значит, что он обязательно вернет единицу:

• 5 и 15: число 5 является простым, а 15 — нет, алгоритм вернет наибольший общий делитель 5.
• 5 и 21: число 5 — простое, а 21 — нет, будет возвращена единица, потому что 21 не делится на 5.
• 3 и 21: число 3 — простое, 21 — нет, будет возвращено число 3, потому что 21 делится на 3.

Исходя из этого, можно сказать, что алгоритм Евклида со 100%-ой вероятностью возвращает единицу в том случае, если на вход переданы два простых числа не равных друг другу.

Примеры разложения на простые множители

Сейчас мы подробно разберем примеры разложения чисел на простые множители. При разложении будем применять алгоритм из предыдущего пункта. Начнем с простых случаев, и постепенно их будем усложнять, чтобы столкнуться со всеми возможными нюансами, возникающими при разложении чисел на простые множители.

Пример.

Разложите число 78 на простые множители.

Решение.

Начинаем поиск первого наименьшего простого делителя p₁ числа a=78. Для этого начинаем последовательно перебирать простые числа из таблицы простых чисел. Берем число 2 и делим на него 78, получаем 78:2=39. Число 78 разделилось на 2 без остатка, поэтому p₁=2 – первый найденный простой делитель числа 78. В этом случае a₁=a:p₁=78:2=39. Так мы приходим к равенству a=p₁·a₁ имеющему вид 78=2·39. Очевидно, что a₁=39 отлично от 1, поэтому переходим ко второму шагу алгоритма.

Теперь ищем наименьший простой делитель p₂ числа a₁=39. Начинаем перебор чисел из таблицы простых чисел, начиная с p₁=2. Делим 39 на 2, получаем 39:2=19 (ост. 1). Так как 39 не делится нацело на 2, то 2 не является его делителем. Тогда берем следующее число из таблицы простых чисел (число 3) и делим на него 39, получаем 39:3=13. Следовательно, p₂=3 – наименьший простой делитель числа 39, при этом a₂=a₁:p₂=39:3=13. Имеем равенство a=p₁·p₂·a₂ в виде 78=2·3·13. Так как a₂=13 отлично от 1, то переходим к следующему шагу алгоритма.

Здесь нам нужно отыскать наименьший простой делитель числа a₂=13. В поисках наименьшего простого делителя p₃ числа 13 будем последовательно перебирать числа из таблицы простых чисел, начиная с p₂=3. Число 13 не делится на 3, так как 13:3=4 (ост. 1), также 13 не делится на 5, 7 и на 11, так как 13:5=2 (ост. 3), 13:7=1 (ост. 6) и 13:11=1 (ост. 2). Следующим простым числом является 13, и на него 13 делится без остатка, следовательно, наименьший простой делитель p₃ числа 13 есть само число 13, и a₃=a₂:p₃=13:13=1. Так как a₃=1, то этот шаг алгоритма является последним, а искомое разложение числа 78 на простые множители имеет вид 78=2·3·13 (a=p₁·p₂·p₃).

Ответ:

78=2·3·13.

Пример.

Представьте число 83 006 в виде произведения простых множителей.

Решение.

На первом шаге алгоритма разложения числа на простые множители находим p₁=2 и a₁=a:p₁=83 006:2=41 503, откуда 83 006=2·41 503.

На втором шаге выясняем, что 2, 3 и 5 не являются простыми делителями числа a₁=41 503, а число 7 – является, так как 41 503:7=5 929. Имеем p₂=7, a₂=a₁:p₂=41 503:7=5 929. Таким образом, 83 006=2·7·5 929.

Наименьшим простым делителем числа a₂=5 929 является число 7, так как 5 929:7=847. Таким образом, p₃=7, a₃=a₂:p₃=5 929:7=847, откуда 83 006=2·7·7·847.

Дальше находим, что наименьший простой делитель p₄ числа a₃=847 равен 7. Тогда a₄=a₃:p₄=847:7=121, поэтому 83 006=2·7·7·7·121.

Теперь находим наименьший простой делитель числа a₄=121, им является число p₅=11 (так как 121 делится на 11 и не делится на 7). Тогда a₅=a₄:p₅=121:11=11, и 83 006=2·7·7·7·11·11.

Наконец, наименьший простой делитель числа a₅=11 – это число p₆=11. Тогда a₆=a₅:p₆=11:11=1. Так как a₆=1, то этот шаг алгоритма разложения числа на простые множители является последним, и искомое разложение имеет вид 83 006=2·7·7·7·11·11.

Полученный результат можно записать как каноническое разложение числа на простые множители 83 006=2·73·112.

Ответ:

83 006=2·7·7·7·11·11=2·73·112

Пример.

Разложите на простые множители число 897 924 289.

Решение.

В этом примере чтобы найти первый простой множитель разложения, придется перебрать все простые числа, начиная с 2. Этот долгий перебор заканчивается на числе 937. То есть, p₁=937, тогда a₁=a:p₁=897 924 289:937=958 297 и 897 924 289=937·958 297.

На втором шаге алгоритма уже бы пришлось перебирать меньше простых чисел, чем на первом шаге. Здесь мы бы начали с p₁=937, а число 967 уже является простым делителем числа a₁=958 297. То есть, p₂=967, тогда a₂=a₁:p₁=958 297:967=991 и 897 924 289=937·967·991.

На третьем шаге мы можем сразу сказать, что 991 – простое число. Действительно, оно не имеет ни одного простого делителя, не превосходящего ( можно грубо оценить как , так как очевидно, что 991<402), то есть, наименьшим делителем числа 991 является оно само. Тогда p₃=991 и a₃=a₂:p₃=991:991=1. Следовательно, искомое разложение числа 897 924 289 на простые множители имеет вид 897 924 289=937·967·991.

Ответ:

897 924 289=937·967·991.

Пример. Разложение числа 150 на простые множители

	Раз­ло­жим число 150 на мно­жи­те­ли. На­при­мер, 150 – это 15 умно­жить на 10. 15 – это со­став­ное число. Его можно раз­ло­жить на про­стые мно­жи­те­ли 5 и 3. 10 – это со­став­ное число. Его можно раз­ло­жить на про­стые мно­жи­те­ли 5 и 2. За­пи­сав вме­сто 15 и 10 их раз­ло­же­ния на про­стые мно­жи­те­ли, мы по­лу­чи­ли раз­ло­же­ние числа 150.
	Число 150 можно по-дру­го­му раз­ло­жить на мно­жи­те­ли. На­при­мер, 150 – это про­из­ве­де­ние чисел 5 и 30. 5 – число про­стое. 30 – это число со­став­ное. Его можно пред­ста­вить как про­из­ве­де­ние 10 и 3. 10 – число со­став­ное. Его можно раз­ло­жить на про­стые мно­жи­те­ли 5 и 2. Мы по­лу­чи­ли раз­ло­же­ние числа 150 на про­стые мно­жи­те­ли дру­гим спо­со­бом.
	За­ме­тим, что пер­вое и вто­рое раз­ло­же­ние оди­на­ко­вы. Они от­ли­ча­ют­ся толь­ко по­ряд­ком сле­до­ва­ния мно­жи­те­лей. При­ня­то за­пи­сы­вать мно­жи­те­ли в по­ряд­ке воз­рас­та­ния.
Вся­кое со­став­ное число можно раз­ло­жить на про­стые мно­жи­те­ли един­ствен­ным об­ра­зом с точ­но­стью до по­ряд­ка мно­жи­те­лей.

Минутка истории

Интерес ученых к простым числам проснулся в третьем веке до нашей эры. Первым заинтересовался Евклид, нашел доказательство, что ряд простых чисел бесконечен. К сожалению,перечень известных, пополнялся новыми, очень медленно, пока не появились первые вычислительные машины, самостоятельно подбирающие делители к огромным числовым значениям. В 1952 г. самое большое простое числовое значение, известное науке содержало 157 цифр, уже в 1985 году количество цифр стало 65050. Сегодня, математики продолжают работать над этим вопросом. Результатом проделанной работы стало открытие американскими учеными нового, самого большого простого числового значения, состоящего из 65087 цифр. Научные сотрудники более 12 месяцев проверяли, подходящие под требования числовые значения. Проверено более 350000 чисел, подобрано несколько миллиардов различных делителей.

В декабре 2018,  американский разработчик Патрик Ларош, побил мировые рекорды и открыл наибольшее простое число 282 589 933 – 1. Количество цифр этого числа равно 24 862 048. За свое открытие Патрик получил премию в размере 2 миллионов долларов.

Алгоритм разложения числа на простые множители

Чтобы успешно справиться с задачей разложения числа на простые множители, нужно очень хорошо владеть информацией статьи простые и составные числа .

Суть процесса разложения целого положительного и превосходящего единицу числа a
понятна из доказательства основной теоремы арифметики . Смысл состоит в последовательном нахождении наименьших простых делителей p 1 , p 2 , …,p n
чисел a, a 1 , a 2 , …, a n-1
, что позволяет получить ряд равенств a=p 1 ·a 1
, где a 1 =a:p 1
, a=p 1 ·a 1 =p 1 ·p 2 ·a 2
, где a 2 =a 1:p 2
, …, a=p 1 ·p 2 ·…·p n ·a n
, где a n =a n-1:p n
. Когда получается a n =1
, то равенство a=p 1 ·p 2 ·…·p n
даст нам искомое разложение числа a
на простые множители. Здесь же следует заметить, что p 1 ≤p 2 ≤p 3 ≤…≤p n
.

Осталось разобраться с нахождением наименьших простых делителей на каждом шаге, и мы будем иметь алгоритм разложения числа на простые множители. Находить простые делители нам поможет таблица простых чисел . Покажем, как с ее помощью получить наименьший простой делитель числа z
.

Последовательно берем простые числа из таблицы простых чисел (2
, 3
, 5
, 7
, 11
и так далее) и делим на них данное число z
. Первое простое число, на которое z
разделится нацело, и будет его наименьшим простым делителем. Если число z
простое, то его наименьшим простым делителем будет само число z
. Здесь же следует напомнить, что если z
не является простым числом, то его наименьший простой делитель не превосходит числа , где — из z
. Таким образом, если среди простых чисел, не превосходящих , не нашлось ни одного делителя числа z
, то можно делать вывод о том, что z
– простое число (более подробно об этом написано в разделе теории под заголовком данное число простое или составное).

Для примера покажем, как найти наименьший простой делитель числа 87
. Берем число 2
. Делим 87
на 2
, получаем 87:2=43 (ост. 1)
(если необходимо, смотрите статью ). То есть, при делении 87
на 2
получается остаток 1
, поэтому 2
– не является делителем числа 87
. Берем следующее простое число из таблицы простых чисел, это число 3
. Делим 87
на 3
, получаем 87:3=29
. Таким образом, 87
делится на 3
нацело, следовательно, число 3
является наименьшим простым делителем числа 87
.

Заметим, что в общем случае для разложения на простые множители числа a
нам потребуется таблица простых чисел до числа, не меньшего, чем . К этой таблице нам придется обращаться на каждом шаге, так что ее нужно иметь под рукой. Например, для разложения на простые множители числа 95
нам будет достаточно таблицы простых чисел до 10
(так как 10
больше, чем ). А для разложения числа 846 653
уже будет нужна таблица простых чисел до 1 000
(так как 1 000
больше, чем ).

Теперь мы обладаем достаточными сведениями, чтобы записать алгоритм разложения числа на простые множители
. Алгоритм разложения числа a таков:

• Последовательно перебирая числа из таблицы простых чисел, находим наименьший простой делитель p 1
  числа a
  , после чего вычисляем a 1 =a:p 1
  . Если a 1 =1
  , то число a
  – простое, и оно само является своим разложением на простые множители. Если же a 1
  на равно 1
  , то имеем a=p 1 ·a 1
  и переходим к следующему шагу.
• Находим наименьший простой делитель p 2
  числа a 1
  , для этого последовательно перебираем числа из таблицы простых чисел, начиная с p 1
  , после чего вычисляем a 2 =a 1:p 2
  . Если a 2 =1
  , то искомое разложение числа a
  на простые множители имеет вид a=p 1 ·p 2
  . Если же a 2
  на равно 1
  , то имеем a=p 1 ·p 2 ·a 2
  и переходим к следующему шагу.
• Перебирая числа из таблицы простых чисел, начиная с p 2
  , находим наименьший простой делитель p 3
  числа a 2
  , после чего вычисляем a 3 =a 2:p 3
  . Если a 3 =1
  , то искомое разложение числа a
  на простые множители имеет вид a=p 1 ·p 2 ·p 3
  . Если же a 3
  на равно 1
  , то имеем a=p 1 ·p 2 ·p 3 ·a 3
  и переходим к следующему шагу.
• Находим наименьший простой делитель p n
  числа a n-1
  , перебирая простые числа, начиная с p n-1
  , а также a n =a n-1:p n
  , причем a n
  получается равно 1
  . Этот шаг является последним шагом алгоритма, здесь получаем искомое разложение числа a
  на простые множители: a=p 1 ·p 2 ·…·p n
  .

Все результаты, полученные на каждом шаге алгоритма разложения числа на простые множители, для наглядности представляют в виде следующей таблицы, в которой слева от вертикальной черты записывают последовательно в столбик числа a, a 1 , a 2 , …, a n
, а справа от черты – соответствующие наименьшие простые делители p 1 , p 2 , …, p n
.

Осталось лишь рассмотреть несколько примеров применения полученного алгоритма для разложения чисел на простые множители.

Неприводимые множители

Решая различные задачи, можно столкнуться со сложными выражениями, которые, как кажется, разложить нельзя. Например, (2 * p2 — 5 * p — 3)/(3 * p — 9). В числителе дроби находится квадратный трёхчлен, который на самом деле можно разложить. Для того чтобы его можно было упростить, используется формула: ar2 + br + p = a (r — r1) * (r — r2), где r1 и r2 корни выражения.

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

Для рассматриваемого примера дискриминант квадратного уравнения будет равняться: Д = 25 — 4*2 (-3) = 49. Отсюда p1 = (5 + 7)/4 = 3, p2 = (5 — 7)/4 = -½. Подставив полученные корни в формулу, можно запись: 2 * (p — 3) * (p + ½).

Теперь вместо числителя нужно подставить полученное разложение: (2*p2 — 5*p — 3)/(3*p — 9) = 2*(p — 3) * (p + ½)/3 * (p — 3) = (2 *p + 1)/3.