14 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Разложение на множители больших чисел

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

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

Навигация по странице.

Что значит разложить число на простые множители?

Сначала разберемся с тем, что такое простые множители.

Понятно, раз в этом словосочетании присутствует слово «множители», то имеет место произведение каких-то чисел, а уточняющее слово «простые» означает, что каждый множитель является простым числом. Например, в произведении вида 2·7·7·23 присутствуют четыре простых множителя: 2 , 7 , 7 и 23 .

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

Это значит, что данное число нужно представить в виде произведения простых множителей, причем значение этого произведения должно быть равно исходному числу. В качестве примера рассмотрим произведение трех простых чисел 2 , 3 и 5 , оно равно 30 , таким образом, разложение числа 30 на простые множители имеет вид 2·3·5 . Обычно разложение числа на простые множители записывают в виде равенства, в нашем примере оно будет таким: 30=2·3·5 . Отдельно подчеркнем, что простые множители в разложении могут повторяться. Это явно иллюстрирует следующий пример: 144=2·2·2·2·3·3 . А вот представление вида 45=3·15 не является разложением на простые множители, так как число 15 – составное.

Возникает следующий вопрос: «А какие вообще числа можно разложить на простые множители»?

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

Но все ли целые числа, превосходящие единицу, раскладываются на простые множители?

Понятно, что простые целые числа разложить на простые множители нет возможности. Это объясняется тем, что простые числа имеют только два положительных делителя – единицу и самого себя, поэтому они не могут быть представлены в виде произведения двух или большего количества простых чисел. Если бы целое число z можно было бы представить в виде произведения простых чисел a и b , то понятие делимости позволило бы сделать вывод, что z делится и на a и на b , что невозможно в силу простоты числа z. Однако считают, что любое простое число само является своим разложением.

А как насчет составных чисел? Раскладываются ли составные числа на простые множители, и все ли составные числа подлежат такому разложению? Утвердительный ответ на ряд этих вопросов дает основная теорема арифметики. Основная теорема арифметики утверждает, что любое целое число a , которое больше 1 , можно разложить на произведение простых множителей p1, p2, …, pn , при этом разложение имеет вид a=p1·p2·…·pn , причем это разложение единственно, если не учитывать порядок следования множителей

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

В разложении числа простые множители могут повторяться. Повторяющиеся простые множители можно записать более компактно, используя степень числа. Пусть в разложении числа a простой множитель p1 встречается s1 раз, простой множитель p2 – s2 раз, и так далее, pn – sn раз. Тогда разложение на простые множители числа a можно записать как a=p1 s1 ·p2 s2 ·…·pn sn . Такая форма записи представляет собой так называемое каноническое разложение числа на простые множители.

Приведем пример канонического разложения числа на простые множители. Пусть нам известно разложение 609 840=2·2·2·2·3·3·5·7·11·11 , его каноническая форма записи имеет вид 609 840=2 4 ·3 2 ·5·7·11 2 .

Каноническое разложение числа на простые множители позволяет найти все делители числа и число делителей числа.

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

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

Суть процесса разложения целого положительного и превосходящего единицу числа a понятна из доказательства основной теоремы арифметики. Смысл состоит в последовательном нахождении наименьших простых делителей 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 даст нам искомое разложение числа a на простые множители. Здесь же следует заметить, что p1≤p2≤p3≤…≤pn .

Осталось разобраться с нахождением наименьших простых делителей на каждом шаге, и мы будем иметь алгоритм разложения числа на простые множители. Находить простые делители нам поможет таблица простых чисел. Покажем, как с ее помощью получить наименьший простой делитель числа 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 таков:

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

Все результаты, полученные на каждом шаге алгоритма разложения числа на простые множители, для наглядности представляют в виде следующей таблицы, в которой слева от вертикальной черты записывают последовательно в столбик числа a, a1, a2, …, an , а справа от черты – соответствующие наименьшие простые делители p1, p2, …, pn .

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

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

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

umath.ru

Изучаем математику вместе!

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

Натуральное число называется делителем целого числа если для подходящего целого числа верно равенство . В этом случае говорят, что делится на или что число кратно числу .

Простым числом называют натуральное число , делящееся только на себя и на единицу. Составным числом называют число, имеющее больше двух различных делителей (любое натуральное число не равное имеет как минимум два делителя: и ). Например, числа – простые, а числа – составные.

Данная программа раскладывает число в произведение простых множителей онлайн. Разложить число на множители онлайн с её помощью очень просто.

Как разложить число на множители?

В школе на уроках математики разложение числа на множители обычно записывают столбиком (в две колонки). Делается это так: в левую колонку выписываем исходное число, затем

  • Берём самое маленькое простое число — 2 и по признакам делимости или обычным делением проверяем, делится ли исходное число на 2.
  • Если делится, то в правую колонку выписываем 2. Далее делим исходное число на 2 и записываем результат в левую колонку под исходным числом.
  • Если не делится, то берём следующее простое число — 3.

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

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

Решение. Записываем число 84 в левую колонку:

Берём первое простое число — два и проверяем, делится ли 84 на 2. Так как 84 оканчивается на 4, а 4 делится на 2, то и 84 делится на 2 по признаку делимости. Записываем 2 в правую колонку. 84:2 = 42, число 42 записываем в левую колонку. Получили вот что:

Теперь работаем уже с числом 42. Число 42 делится на 2, поэтому записываем 2 в правую колонку, 42:2 = 21, число 21 записываем в левую колонку.

Число 21 на 2 не делится, поэтому проверяем его делимость на следующее простое число — 3. Число 21 делится на 3, 21:3 = 7. Записали 3 в правую колонку, 7 — в левую. Получили

Число 7 — простое число, поэтому в правой колонке записываем 7, в левую пишем 1. В итоге получили:

Всё, число разложено!

В результате в правой колонке оказались записаны все простые множители числа 84. То есть 84=2∙2∙3∙7.

О калькуляторе

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

Разложение числа на простые множители онлайн : 13 комментариев

Программа хорошая. Один вопрос. На каком языке написана программа?

  1. Андрей Автор записи 10.02.2016 в 20:18

Анастасия, на javascript.

Супер! Болела- пропустила тему. Оч помогло

Результат: Число 18014398241046528 — простое.

Согласен, что заданное число — простое, но в результате вообще указано четное число. 🙂

  1. Андрей Автор записи 06.10.2019 в 19:37

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

Я не понимаю хоть убейте — что такое «с точностью до порядка следования сомножителей»?? Что за «порядок»?? Какого ещё «следования»??
> 90 == 5 * 3 * 3 * 2.
Что здесь «порядок следования»??
Ну вот другой порядок следования, и чего?:
> 90 == 2 * 3 * 5 * 3.

  1. Андрей Автор записи 02.09.2019 в 12:42

> 90 == 5 * 3 * 3 * 2.
> 90 == 2 * 3 * 5 * 3.

Формулировка «с точностью до порядка следования сомножителей» означает, что нам важен не порядок, в котором идут простые множители числа, а важно количество раз, которое каждый простой множитель встречается в разложении числа.

В примере с числом 90 в разложении присутствует один множитель 2, два множителя 3 и один множитель 5. Когда говорят, что разложение единственно, то имеют в виду, что не существует разложения числа 90, в котором было бы, например, два множителя 2.

Добрый день! 6 класс, задание на контрольной. Необходимо разложить число 253 426. Возможно ли без нескончаемых проверок на деление определить, что число 126 713 (результат деления заданного числа на 2) и есть простой множитель?

Не понимаю, как можно поставить такую задачу в 6-м классе… Либо неверно истолковано условие, либо я слишком «закостенел»:
1. Все методы проверки числа на простоту — вероятностные (т.е. не 100%-ные)
2. Грубо говоря, есть только 3 рабочих метода разложения чисел на множители:
— последовательный перебор;
— метод Ферма (, где — ваше число, а — округлённый вверх корень из числа );
— квадратичное решето (это экзотика для разложения чисел от 100 разрядов и выше, иначе первые два метода сработают быстрее).

  1. Андрей Автор записи 06.10.2019 в 19:21

Да, полностью согласен с Шуриком, мы не знаем способа, который позволил бы с уверенностью определить, что число 126 713 является простым, не прибегая к многочисленным проверкам на деление.

На мой взгляд, самым быстрым способом в данном случае является проверка, делится ли 126 713 на простые числа от 2 до . Делители проверяем только до квадратного корня потому, что если число составное, то его можно представить как произведение где и — целые числа больше 1, и одно из этих чисел точно не больше .

Всего имеется 71 простых чисел, не превышающих 355, но вручную за разумное время проверить делимость на 71 число не представляется возможным.

Существует тест Агравала — Каяла — Саксены, позволяющий протестировать число на простоту быстрее описанного выше алгоритма — но есть несколько НО — этот тест хорошо работает на компьютере и для действительно больших чисел.

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

Данная статья дает ответы на вопрос о разложении числа на простыне множители. Рассмотрим общее представление о разложении с примерами. Разберем каноническую форму разложения и его алгоритм. Будут рассмотрены все альтернативные способы при помощи использования признаков делимости и таблицы умножения.

Что значит разложить число на простые множители?

Разберем понятие простые множители. Известно, что каждый простой множитель – это простое число. В произведении вида 2 · 7 · 7 · 23 имеем, что у нас 4 простых множителя в виде 2 , 7 , 7 , 23 .

Разложение на множители предполагает его представление в виде произведений простых. Если нужно произвести разложение числа 30 , тогда получим 2 , 3 , 5 . Запись примет вид 30 = 2 · 3 · 5 . Не исключено, что множители могут повторяться. Такое число как 144 имеет 144 = 2 · 2 · 2 · 2 · 3 · 3 .

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

При z , относящемуся к целым числам, представляется в виде произведения а и b , где z делится на а и на b . Составные числа раскладывают на простые множители при помощи основной теоремы арифметики. Если число больше 1 , то его разложение на множители p 1 , p 2 , … , p n принимает вид a = p 1 , p 2 , … , p n . Разложение предполагается в единственном варианте.

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

При разложении множители могут повторяться. Их запись выполняется компактно при помощи степени. Если при разложении числа а имеем множитель p 1 , который встречается s 1 раз и так далее p n – s n раз. Таким образом разложение примет вид a=p1 s 1· a = p 1 s 1 · p 2 s 2 · … · p n s n . Эта запись имеет название канонического разложения числа на простые множители.

При разложении числа 609840 получим, что 609 840 = 2 · 2 · 2 · 2 · 3 · 3 · 5 · 7 · 11 · 11 ,его канонический вид будет 609 840 = 2 4 · 3 2 · 5 · 7 · 11 2 . При помощи канонического разложения можно найти все делители числа и их количество.

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

Чтобы правильно разложить на множители необходимо иметь представление о простых и составных числах. Смысл заключается в том, чтобы получить последовательное количество делителей вида 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 получим искомое разложение числа а на простые множители. Заметим, что p 1 ≤ p 2 ≤ p 3 ≤ … ≤ p n .

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

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

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

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

  • нахождение наименьшего множителя при делителе p 1 числа a по формуле a 1 = a : p 1 , когда a 1 = 1 , тогда а является простым числом и включено в разложение на множители, когда не равняется 1 , тогда a = p 1 · a 1 и следуем к пункту, находящемуся ниже;
  • нахождение простого делителя p 2 числа a 1 при помощи последовательного перебора простых чисел, используя a 2 = a 1 : p 2 ,когда a 2 = 1 , тогда разложение примет вид a = p 1 · p 2 ,когда a 2 = 1 , тогда a = p 1 · p 2 · a 2 , причем производим переход к следующему шагу;
  • перебор простых чисел и нахождение простого делителя p 3 числа a 2 по формуле a 3 = a 2 : p 3 , когда a 3 = 1 , тогда получим, что a = p 1 · p 2 · p 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 = p 1 · p 2 · … · p n .

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

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

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

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

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

Решение

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

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

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

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

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

Решение

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

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

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

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

Для числа a 5 = 11 число p 6 = 11 является наименьшим простым делителем. Отсюда a 6 = a 5 : p 6 = 11 : 11 = 1 . Тогда a 6 = 1 . Это указывает на завершение алгоритма. Множители запишутся в виде 83 006 = 2 · 7 · 7 · 7 · 11 · 11 .

Каноническая запись ответа примет вид 83 006 = 2 · 7 3 · 11 2 .

Ответ: 83 006 = 2 · 7 · 7 · 7 · 11 · 11 = 2 · 7 3 · 11 2 .

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

Решение

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

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

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

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

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

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

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

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

При разложении числа 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 = 2 3 · 5 2 · 17 .

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

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

Простой множитель – это множитель, который представляет собой простое число.

Любое составное число можно представить в виде произведения простых чисел.

Пример. Представим в виде произведения простых множителей числа 4, 6 и 8:

Правые части полученных равенств называются разложением на простые множители.

Разложение на простые множители – это представление составного числа в виде произведения простых множителей.

Разложить составное число на простые множители – значит представить это число в виде произведения простых множителей.

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

24 = 2 · 2 · 2 · 3 = 2 3 · 3

Примечание. Простые множители обычно записывают в порядке их возрастания.

Как разложить число на простые множители

Последовательность действий при разложении числа на простые множители:

  1. Проверяем по таблице простых чисел, не является ли данное число простым.
  2. Если нет, то последовательно подбираем самое маленькое простое число из таблицы простых чисел, на которое данное число делится без остатка, и выполняем деление.
  3. Проверяем по таблице простых чисел, не является ли полученное частное простым числом.
  4. Если нет, то последовательно подбираем самое маленькое простое число из таблицы простых чисел, на которое полученное частное делится нацело, и выполняем деление.
  5. Повторяем пункты 3 и 4 до тех пор, пока в частном не получится единица.

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

Начинаем поиск наименьшего простого делителя числа 102. Для этого последовательно подбираем самое маленькое простое число из таблицы простых чисел, на которое 102 разделится без остатка. Берём число 2 и пробуем разделить на него 102, получаем:

Число 102 разделилось на 2 без остатка, поэтому 2 – первый найденный простой множитель. Так как делимое равно делителю, умноженному на частное, то можно написать:

Переходим к следующему шагу. Проверяем по таблице простых чисел, не является ли полученное частное простым числом. Число 51 составное. Начиная с числа 2, подбираем из таблицы простых чисел наименьший простой делитель числа 51. Число 51 не делится нацело на 2. Переходим к следующему числу из таблицы простых чисел (к числу 3) и пробуем разделить на него 51, получаем:

Число 51 разделилось на 3, поэтому 3 – второй найденный простой множитель. Теперь мы можем и число 51 представить в виде произведения. Этот процесс можно записать так:

102 = 2 · 51 = 2 · 3 · 17

Проверяем по таблице простых чисел, не является ли полученное частное простым числом. Число 17 простое. Значит наименьшим простым числом, на которое делится 17, будет само это число:

Так как в частном у нас получилась единица, то разложение закончено. Таким образом, разложение числа 102 на простые множители имеет вид:

Ответ: 102 = 2 · 3 · 17.

В арифметике имеется ещё другая форма записи, облегчающая процесс разложения составных чисел. Она состоит в том, что весь процесс разложения записывают столбиком (в две колонки, разделённых вертикальной чертой). Слева от вертикальной черты, сверху вниз, записывают последовательно: данное составное число, затем получающиеся частные, а справа от черты – соответствующие наименьшие простые делители.

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

Пишем число 120 и справа от него проводим вертикальную черту:

Справа от черты записываем самый маленький простой делитель числа 120:

Выполняем деление и получившееся частное (60) записываем под данным числом:

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

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

Ответ: 120 = 2 3 · 3 · 5.

Составное число разлагается на простые множители единственным образом.

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

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

Как раскладывать числа на множители?

Любое составное число можно представить в виде произведения его простых делителей:

Правые части полученных равенств называют разложением на простые множители чисел 15 и 28.

Разложить данное составное число на простые множители – значит представить это число в виде произведения его простых делителей.

Разложение данного числа на простые множители выполняется следующим образом:

  1. Сначала нужно подобрать самое маленькое простое число из таблицы простых чисел, на которое данное составное число делится без остатка, и выполнить деление.
  2. Далее, нужно опять подобрать самое маленькое простое число, на которое уже полученное частное будет делиться без остатка.
  3. Выполнение второго действия повторяют до тех пор, пока в частном не получится единица.

В качестве примера, разложим на простые множители число 940. Находим наименьшее простое число, на которое делится 940. Таким числом является 2:

Теперь подбираем наименьшее простое число, на которое делится 470. Таким числом является опять 2:

Наименьшее простое число, на которое делится 235 – это 5:

Число 47 простое, значит наименьшим простым числом, на которое делится 47, будет само это число:

Таким образом, мы получаем число 940, разложенное на простые множители:

940 = 2 · 470 = 2 · 2 · 235 = 2 · 2 · 5 · 47

Если в разложении числа на простые множители получилось несколько одинаковых сомножителей, то для краткости, их можно записать в виде степени:

940 = 2 2 · 5 · 47

Разложение на простые множители удобнее всего записывать следующим образом: сначала записываем данное составное число и справа от него проводим вертикальную черту:

Справа от черты записываем самый маленький простой делитель, на который делится данное составное число:

Выполняем деление и получившееся в результате деления частное записываем под делимым:

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

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

Попробуем к примеру разложить на простые множители число 5106:

Дойдя до частного 851, трудно с ходу определить его наименьший делитель. Обращаемся к таблице простых чисел. Если в ней найдётся число, поставившее нас в затруднение, значит оно делится только на себя и на единицу. Числа 851 нет в таблице простых чисел, значит, оно является составным. Остаётся только методом последовательного перебора делить его на простые числа: 3, 7, 11, 13, . и так до тех пор, пока не найдём подходящего простого делителя. Методом перебора находим, что 851 делится на число 23:

Таким образом, получаем число 5106, разложенное на простые множители:

5106 = 2 · 3 · 23 · 37

Калькулятор разложения на множители

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

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

12.3. Разложение на множители

Разложение на множители — предмет непрерывного исследования в прошлом; и такие же исследования, вероятно, продолжатся в будущем. Разложение на множители играет очень важную роль в безопасности некоторых криптосистем с открытым ключом (см. лекции 14-15).

Основная теорема арифметики

Согласно Основной теореме арифметики любое положительное целое число больше единицы может быть уникально записано в следующей главной форме разложения на множители, где p1, p2, . pk — простые числа и e1, e2, . ek — положительные целые числа.

Есть непосредственные приложения разложения на множители, такие как вычисление наибольшего общего делителя и наименьшего общего множителя.

Наибольший общий делитель

В «Модульная арифметика» мы уже обсуждали наибольший общий делитель двух номеров, НОД (a, b) . Посмотрите, как евклидов алгоритм дает это значение, но это значение может также быть найдено, если мы знаем разложение на множители чисел a и b .

Наименьшее общее кратное

Наименьшее общее кратное, НОК (a, b) , — наименьшее целое число, кратное числам a и b . Используя разложение, мы также находим НОК (a, b) .

Может быть доказано, что НОД (a,b) и НОК (a,b) связаны с друг другом, как это показано ниже:

Методы разложения на множители

Поиск эффективных алгоритмов для разложения на множители больших составных чисел ведется давно. К сожалению, совершенный алгоритм для этого пока не найден. Хотя есть несколько алгоритмов, которые могут разложить число на множители, ни один не способен провести разложение достаточно больших чисел в разумное время. Позже мы увидим, что это хорошо для криптографии, потому что современные криптографические системы полагаются на этот факт. В этой секции мы даем несколько простых алгоритмов, которые проводят разложение составного числа. Цель состоит в том, чтобы сделать процесс разложения на множители менее трудоёмким.

Метод проверки делением

Самый простой и наименее эффективный алгоритм — метод разложения на множители проверкой делением. Мы просто пробуем все положительные целые числа начиная с 2 , для того чтобы найти одно, которое делит n . После обсуждения решета Эратосфена мы знаем, что если n составное, то делитель будет простым числом . Алгоритм 12.3 показывает этот метод. Алгоритм имеет два цикла: один внешний и один внутренний, находит уникальные множители в разложении; внутренняя петля находит повторяющиеся множители разложения. Например, . Внешний цикл множители 2 и 3 . Внутренний цикл находит, что число 2 множитель.

Сложность. Метод проверки делением обычно хорош, если n 10 , но он неэффективен и неосуществим для разложения больших целых чисел. Сложность алгоритма (приложение L) показательна.

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

Мы выполняем программу, основанную на алгоритме, и получаем следующий результат:

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

Мы выполняем программу, основанную на алгоритме, и получаем следующий результат:

Метод Ферма

Метод Ферма разложения на множители (алгоритм 12.4) делит номер n на два положительных целых числа ( a и b — не обязательно простые числа) так, чтобы .

Метод Ферма основан на факте, что если мы можем найти x и y , такие, что n = x 2 – y 2 , тогда мы имеем

Метод сводится к попытке найти два целых числа a и b , близкие друг к другу (). Начинаем с наименьшего целого числа, большего, чем . Потом пробуем найти другое целое число y , такое, чтобы выполнялось уравнение y 2 = x 2 – n . В каждой итерации мы должны рассмотреть, является ли результат x 2 – n полным квадратом. Если мы находим такое значение для y, мы вычисляем a и b и выходим из цикла. Если мы не делаем этого, мы проводим другую итерацию.

Заметим, что метод не обязательно находит разложение на простые числа ( каноническое разложение ); алгоритм должен быть повторен рекурсивно для каждого из значений a и b , пока не будут найдены сомножители в виде простых чисел.

Сложность. Сложность метода Ферма является близкой к показательному закону (см. приложение L).

p – 1 Метод Полларда

В 1974 г. Джон Поллард разработал метод, который находит разложение числа p на простые числа. Метод основан на условии, что p – 1 не имеет сомножителя, большего, чем заранее определенное значение B , называемое границей. Алгоритм Полларда показывает, что в этом случае

Алгоритм 12.5 показывает псевдокод для p – 1 метода Полларда разложения на множители. Когда мы выходим из второго цикла, в a сохраняется 2 B! .

Сложность. Заметим, что этот метод требует сделать B – 1 операций возведения в степень (a = a e mod n) . Как мы увидим позже в этой лекции, есть быстрый алгоритм возведения в степень, который выполняет это за 2 1og2 B операций. Метод также использует вычисления НОД , который требует n 3 операций. Мы можем сказать, что сложность — так или иначе больше, чем O(B) или O(2 n ) , где nb — число битов в B . Другая проблема – этот алгоритм может заканчиваться сигналом об ошибке. Вероятность успеха очень мала, если B имеет значение, не очень близкое к величине .

Используя p – 1 метод Полларда, найдите сомножители числа 57247159 с границей B = 8 .

Мы выполняем программу, основанную на рассмотренном выше алгоритме, и находим, что p = 421 . Фактически . Обратите внимание, что 421 — простое число и p –1 не имеет ни одного сомножителя, большего 8 , т.е. ().

Ссылка на основную публикацию
Adblock
detector