что такое разложение числа
Множитель. Разложение числа на множители Факторизация.
Простые и составные числа.
Все целые числа (кроме 0 и 1) имеют минимум два делителя: 1 и самого себя. Числа, не имеющие других делителей, называются простыми числами. Числа, имеющие другие делители, называются составными (или сложными) числами. Простых чисел – бесконечное множество. Ниже приведены простые числа, не превосходящие 200:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101,
103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197, 199.
Умножение — одно из четырёх основных арифметических действий, бинарная математическая операция, в которой один аргумент складывается столько раз, сколько показывает другой. В арифметике под умножением понимают краткую запись сложения указанного количества одинаковых слагаемых.
Например, запись 5*3 обозначает «сложить три пятёрки», то есть 5+5+5. Результат умножения называется произведением, а умножаемые числа — множителями или сомножителями. Первый множитель иногда называется «множимое».
Всякое составное число можно разложить на простые множители. При любом способе получается одно и то же разложение, если не учитывать порядка записи множителей.
Разложение числа на множители ( Факторизация ).
Разложение на множители (факторизация) – перебор делителей — алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей.
Т.е., простым языком, факторизация – это название процесса разложения чисел на множители, выраженное научным языком.
Последовательность действий при разложении на простые множители:
1. Проверяем, не является ли предложенное число простым.
2. Если нет, то подбираем, руководствуясь признаками деления делитель, из простых чисел начиная с наименьшего (2, 3, 5 …).
3. Повторяем это действие до тех пор, пока частное не окажется простым числом.
Разложим на простые множители число 27 :
Математика
Именная карта банка для детей
с крутым дизайном, +200 бонусов
Закажи свою собственную карту банка и получи бонусы
План урока:
Все вещи можно представить в виде чисел.
Рассмотрим привычный всем карандаш. Привычный, обыденный предмет. Большинство людей даже не задумываются, из чего он состоит.
На самом деле, для изготовления карандаша понадобится древесина, грифель, краска. И это самый простейший перечень составляющих. Ведь собственные составляющие имеют краска, грифель, древесина. Поэтому список компонентов, необходимых для изготовления обычного карандаша, можно продолжать очень долго. Точно так происходит и с математическими числами. Каждое число имеет свой состав, в зависимости от состава – название.
А из чего состоят числа? Какие бывают? Как разложить число? На эти и многие другие вопросы ищите ответы в нашем уроке!
Простые и составные числа
На столе лежало 2 яблока, 4 апельсина. Сколько детей, смогут полакомиться, каждым видом фруктов?
Чтобы ответить на главный вопрос задачи нужно выяснить на какое количество человек можно разделить фрукты, не деля их на части (целыми).
В математике такие числа называют простыми
Получается, четыре мы можем разделить на 1, на само себя и еще на два. Такой вид чисел в арифметике называют составными:
Разложение на простые множители
В математике возникают ситуации, когда для выполнения определенных вычислений нужно знать, какие множители входят в состав того, или иного числа.
Например в состав 6, входит два простых множителя:
А как быть с большими числами, в записи, которых 2 и более знака? Как правильно выполнять и записывать разложение на простые множители?
Что значит «Разложить на простые множители?».
В арифметике для выполнения разложения на простые множители, существует специальный вид записи и алгоритм действий.
Давайте рассмотрим алгоритм действий:
Запись разложения числа на простые множители выполняется столбиком, состоящим из двух колонок. В правой колонке записываем делимое и полученное частное, в левой – пишем подходящие, простые делители. Между собой колонки разделены вертикальной чертой:
Разложим на множители число 20.
Для выполнения данного задания, используем рассмотренный алгоритм.
20 можно разделить на: 1, 2, 4, 5, 10,20.
Мы подобрали шесть делителей, значит, делимое, является составным числом.
Для этого вспоминаем изученные признаки делимости, и проверяем данное число.
Начнем с наименьшего простого числа 2
Делимое 20 оканчивается цифрой 0, значит, оно делится без остатка на 2.
Далее, подбираем делитель к полученному частному. Опять начинаем с наименьшего простого числа 2. Так как запись 10, оканчивается 0, по признаку делимости, число делится на 2 без остатка:
В результате мы получили простое число, которое можно разделить, только на само себя (на 1 деление не выполняем, оно не является простым числом).
Когда в частном получилась единица, то говорят, разложение числа на простые множители окончено.
Давайте запишем данную математическую операцию.
Выполнять запись будем в столбик.
Сначала записываем делимое и проводим вертикальную черту.
Рядом, с правой стороны, пишем первый делитель.
Выполняем деление и записываем частное под делимым.
После, снова подбираем делитель к полученному частному, справа пишем подходящий делитель. Выполняем деление до тех пор, пока в результате не увидим 1.
Выходит, 20 = 2×2×5. Полученное выражение можно записать немного иначе. В записи использовано два одинаковых множителя, повторяющихся два раза. Используя определение степени
Ничего сложного. Главное – запомнить порядок действий!
Рассмотрим еще один пример.
Разложим число 156.
Чтобы выполнить данное задание используем правило разложения числа на простые множители.
Выполняем деление и частное запишем под делимым: 156 : 2 = 78.
Полученное частное (78) оканчивается четной цифрой, следовательно,делится на 2. Рядом записываем делитель, выполняем деление:
Новый результат оканчивается нечетной цифрой, поэтому на два разделить нельзя. Смотрим, подойдет ли в качестве делителя следующее – 3. Вспоминаем признак делимости на 3:
В записи 39 использованы цифры 3,9. Найдем их сумму:
Полученная сумма делится на 3, следовательно, все число делится на 3.
Записываем делитель и выполняем деление 39 : 3 = 13. Частное, пишем в левый столбик:
Частное 13 – простое, делится на 1 и на само себя. Поэтому:
Разложение на простые множители выполнено.
Очень важно запомнить рассмотренные определения и алгоритм, так как умение раскладывать число на простые множители пригодится вам в течение всего учебного процесса!
Минутка истории
Интерес ученых к простым числам проснулся в третьем веке до нашей эры. Первым заинтересовался Евклид, нашел доказательство, что ряд простых чисел бесконечен. К сожалению,перечень известных, пополнялся новыми, очень медленно, пока не появились первые вычислительные машины, самостоятельно подбирающие делители к огромным числовым значениям. В 1952 г. самое большое простое числовое значение, известное науке содержало 157 цифр, уже в 1985 году количество цифр стало 65050. Сегодня, математики продолжают работать над этим вопросом. Результатом проделанной работы стало открытие американскими учеными нового, самого большого простого числового значения, состоящего из 65087 цифр. Научные сотрудники более 12 месяцев проверяли, подходящие под требования числовые значения. Проверено более 350000 чисел, подобрано несколько миллиардов различных делителей.
В декабре 2018, американский разработчик Патрик Ларош, побил мировые рекорды и открыл наибольшее простое число 2 82 589 933 – 1. Количество цифр этого числа равно 24 862 048. За свое открытие Патрик получил премию в размере 2 миллионов долларов.
Разложение числа на простые множители
Простой множитель — это множитель, который представляет собой простое число.
Любое составное число можно представить в виде произведения простых чисел.
Пример. Представим в виде произведения простых множителей числа 4, 6 и 8:
Правые части полученных равенств называются разложением на простые множители.
Разложение на простые множители — это представление составного числа в виде произведения простых множителей.
Разложить составное число на простые множители — значит представить это число в виде произведения простых множителей.
Простые множители в разложении числа могут повторяться. Повторяющиеся простые множители можно записывать более компактно — в виде степени.
24 = 2 · 2 · 2 · 3 = 2 3 · 3.
Примечание. Простые множители обычно записывают в порядке их возрастания.
Как разложить число на простые множители
Последовательность действий при разложении числа на простые множители:
Пример. Разложите число 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 разложилось на две двойки и одну пятёрку, то оно и всегда будет так разлагаться независимо от того, начнём ли мы разложение с малых множителей или с больших. Принято начинать разложение с малых множителей, т. е. с двоек, троек и т. д.
Калькулятор разложения на множители
Разложение на множители
В отличие от задачи распознавания простоты числа, факторизация предположительно является сложной задачей.
Содержание
Алгоритмы факторизации
В зависимости от сложности алгоритмы факторизации можно разбить на две группы. Первая группа — экспоненциальные алгоритмы, сложность которых экспоненциально зависит от длины входящих праметров (то есть от длины самого числа в бинарном представлении). Вторая группа — субэкспоненциальные алгоритмы, для обозначения сложности которых принята L-нотация:
где N — число подлежащее факторизации, 0 и c — некоторые константы.
Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел. В то же время факторизация с полиномиальной сложностью возможна на квантовом компьютере с помощью алгоритма Шора.
Экспоненциальные алгоритмы
Субэкспоненциальные алгоритмы
Решето числового поля
В настоящее время самыми эффективными алгоритмами факторизации являются вариации решета числового поля:
Применение в криптографии
Предполагаемая сложность задачи факторизации лежит в основе криптостойкости некоторых алгоритмов шифрования с открытым ключом, таких как
Ссылки
Полезное
Смотреть что такое «Разложение на множители» в других словарях:
разложение на множители — Разложение целого числа на его наибольшие сомножители (главные факторы). [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23] Тематики защита информации EN factoring … Справочник технического переводчика
РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ — многочлена представление его в виде произведения двух или большего числа многочленов низших степеней. Напр.: х2 1 = (х 1)(х + 1) … Большой Энциклопедический словарь
РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ — многочлена, представление его в виде произведения двух или большего числа многочленов низших степеней. Напр.: х2 1 = (х 1)(х + 1) … Энциклопедический словарь
Разложение на множители — многочлена, представление его в виде произведения двух или большего числа многочленов низших степеней, например: х2 1 = (х 1)(х + 1), х2 (a + b) x + ab = (x a)(x b), x4 a4 = (x a)(x + a)(x 2+ a 2). Простейшие приёмы Р. на м.: вынесение… … Большая советская энциклопедия
РАЗЛОЖЕНИЕ НА МНОЖИТЕЛИ — многочлена, представление его в виде произведения двух или большего числа многочленов низших степеней. Напр.: х2 1=(* l)(х+l) … Естествознание. Энциклопедический словарь
разложение на множители на ЭВМ с МКМД-архитектурой — — [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации EN MIMD factorization … Справочник технического переводчика
разложение на множители многочлена — представление его в виде произведения двух или большего числа многочленов низших степеней. Например: х2 1=(х 1)(х+1) … Энциклопедический словарь
РАЗЛОЖЕНИЕ — РАСПАД И РАЗЛОЖЕНИЕ В словарь общерусского литературного языка впиталось много научных и специальных терминов. Выйдя за пределы профессиональной речи, эти термины расширяют свои значения и вовлекаются в новые фразеологические контексты.… … История слов
разложение большого целого числа на множители — — [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации EN large integer factorization … Справочник технического переводчика
Разложение — В Викисловаре есть статья «разложение» Разложение разрушение, распад сложного объекта на составляющие: В химии реакции разложения В биологии, биохимии разложение отмерших животных и растительных остатков под действием бактерий и … Википедия