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

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

Чтобы правильно разложить на множители необходимо иметь представление о простых и составных числах. Смысл заключается в том, чтобы получить последовательное количество делителей вида p1, p2, …,pn чисел a, a1, a2, …, an-1, это дает возможность получить a=p1·a1, где a1=a:p1, a=p1·a1=p1·p2·a2, где a2=a1:p2, …, a=p1·p2·…·pn·an, где an=an-1:pn. При получении an=1, то равенство a=p1·p2·…·pn получим искомое разложение числа а на простые множители. Заметим, что p1≤p2≤p3≤…≤pn.

Для нахождения наименьших общих делителей необходимо использовать таблицу простых чисел. Это выполняется на примере нахождения наименьшего простого делителя числа z. При взятии простых чисел 2,3,5,11 и так далее, причем на них делим число z. Так как z не является простым числом, следует учитывать, что наименьшим простым делителем не будет больше z. Видно, что не существуют делителей z, тогда понятно, что z является простым числом.

Пример 1

Рассмотрим на примере числа 87. При его делении на 2 имеем, что 87:2=43 с остатком равным 1. Отсюда следует, что 2 делителем не может являться, деление должно производиться нацело. При делении на 3 получим, что 87:3=29. Отсюда вывод – 3 является наименьшим простым делителем числа 87.

При разложении на простые множители необходимо пользоваться таблицей простых чисел, где a. При разложении 95 следует использовать около 10 простых чисел, а при 846653 около 1000.

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

  • нахождение наименьшего множителя при делителе p1 числа a по формуле a1=a:p1, когда a1=1, тогда а является простым числом и включено в разложение на множители, когда не равняется 1, тогда a=p1·a1 и следуем к пункту, находящемуся ниже;
  • нахождение простого делителя p2 числа a1 при помощи последовательного перебора простых чисел, используя a2=a1:p2, когда a2=1, тогда разложение примет вид a=p1·p2, когда a2=1, тогда a=p1·p2·a2, причем производим переход к следующему шагу;
  • перебор простых чисел и нахождение простого делителя p3 числа a2 по формуле a3=a2:p3, когда a3=1, тогда получим, что a=p1·p2·p3, когда не равняется 1, тогда a=p1·p2·p3·a3 и производим переход к следующему шагу;
  • производится нахождение простого делителя pn числа an-1 при помощи перебора простых чисел с pn-1, а также an=an-1:pn, где an=1, шаг является завершающим, в итоге получаем, что a=p1·p2·…·pn.

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

Полученный алгоритм можно применять при помощи разложения чисел на простые множители.

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

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

Пример 2

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

Решение

Для того, чтобы найти наименьший простой делитель, необходимо перебрать все простые числа, имеющиеся в 78. То есть 78:2=39. Деление без остатка, значит это первый простой делитель, который обозначим как p1. Получаем, что a1=a:p1=78:2=39. Пришли к равенству вида a=p1·a1, где 78=2·39. Тогда a1=39, то есть следует перейти к следующему шагу.

Остановимся на нахождении простого делителя p2 числа a1=39. Следует перебрать простые числа, то есть 39:2=19 (ост. 1). Так как деление с остатком, что 2 не является делителем. При выборе числа 3 получаем, что 39:3=13. Значит, что p2=3 является наименьшим простым делителем 39 по a2=a1:p2=39:3=13. Получим равенство вида a=p1·p2·a2 в виде 78=2·3·13. Имеем, что a2=13 не равно 1, тогда следует переходит дальше.

Наименьший простой делитель числа a2=13 ищется при помощи перебора чисел, начиная с 3. Получим, что 13:3=4 (ост. 1). Отсюда видно, что 13 не делится на 5,7,11, потому как 13:5=2 (ост. 3), 13:7=1 (ост. 6) и 13:11=1 (ост. 2). Видно, что 13 является простым числом. По формуле выглядит так: a3=a2:p3=13:13=1. Получили, что a3=1, что означает завершение алгоритма. Теперь множители записываются в виде 78=2·3·13(a=p1·p2·p3).

Ответ: 78=2·3·13.

Пример 3

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

Решение

Первый шаг предусматривает разложение на простые множители p1=2 и a1=a:p1=83 006:2=41 503, где 83 006=2·41 503.

Второй шаг предполагает, что 2, 3 и 5 не простые делители для числа a1=41 503, а 7 простой делитель, потому как 41 503:7=5 929. Получаем, что p2=7, a2=a1:p2=41 503:7=5 929. Очевидно, что 83 006=2·7·5 929.

Нахождение наименьшего простого делителя p4 к числу a3=847 равняется 7. Видно, что a4=a3:p4=847:7=121, поэтому 83 006=2·7·7·7·121.

Для нахождения простого делителя числа a4=121 используем число 11, то есть p5=11. Тогда получим выражение вида a5=a4:p5=121:11=11, и 83 006=2·7·7·7·11·11.

Для числа a5=11 число p6=11 является наименьшим простым делителем. Отсюда a6=a5:p6=11:11=1. Тогда a6=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.

Пример 4

Произвести разложение числа 897 924 289 на множители.

Решение

Для нахождения первого простого множителя произвести перебор простых чисел, начиная с 2. Конец перебора приходится на число 937. Тогда p1=937, a1=a:p1=897 924 289:937=958 297 и 897 924 289=937·958 297.

Второй шаг алгоритма заключается в переборе меньших простых чисел. То есть начинаем с числа 937. Число 967 можно считать простым, потому как оно является простым делителем числа a1=958 297. Отсюда получаем, что p2=967, то a2=a1:p1=958 297:967=991 и 897 924 289=937·967·991.

Третий шаг говорит о том, что 991 является простым числом, так как не имеет ни одного простого делителя, который не превосходит 991. Примерное значение подкоренного выражения имеет вид 991<402. Иначе запишем как 991<402. Отсюда видно, что p3=991 и a3=a2:p3=991:991=1. Получим, что разложение числа 897 924 289 на простые множители получается как 897 924 289=937·967·991.

Ответ: 897 924 289=937·967·991.

Использование признаков делимости для разложения на простые множители

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

Пример 5

Если необходимо произвести разложение на множители 10, то по таблице видно: 2·5=10. Получившиеся числа 2 и 5 являются простыми, поэтому они являются простыми множителями для числа 10.

Пример 6

Если необходимо произвести разложение числа 48, то по таблице видно: 48=6·8. Но 6 и 8 – это не простые множители, так как их можно еще разложить как 6=2·3 и 8=2·4. Тогда полное разложение отсюда получается как 48=6·8=2·3·2·4. Каноническая запись примет вид 48=24·3.

Пример 7

При разложении числа 3400 можно пользоваться признаками делимости. В данном случае актуальны признаки делимости на 10 и на 100. Отсюда получаем, что 3 400=34·100, где 100 можно разделить на 10, то есть записать в виде 100=10·10, а значит, что 3 400=34·10·10. Основываясь на признаке делимости получаем, что 3 400=34·10·10=2·17·2·5·2·5. Все множители простые. Каноническое разложение принимает вид 3 400=23·52·17.

Когда мы находим простые множители, необходимо использовать признаки делимости и таблицу умножения. Если представить число 75 в виде произведения множителей, то необходимо учитывать правило делимости на 5. Получим, что 75=5·15, причем 15=3·5. То есть искомое разложение пример вид произведения 75=5·3·5.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *