Что значит простой делитель

Делители и кратные

В данном уроке мы рассмотрим такие понятия как делители и кратные.

Что такое делитель?

Мы знаем, что делитель это число, показывающее на сколько частей нужно разделить делимое. Например, в выражении 8 : 2 = 4, делителем является число 2. Это число показывает на сколько частей нужно разделить число 8. После разделения получается ответ 4. Как видно из примера, число 8 делится на число 2 без остатка. Говорят, что число 2 является делителем числа 8.

Пример 1. Число 2 является делителем числа 8, поскольку 8 делится на 2 без остатка:

Пример 2. Число 3 является делителем числа 9, поскольку 9 делится на 3 без остатка:

Пример 3. Число 4 не является делителем числа 10 поскольку 10 не делится на 4 без остатка:

10 : 4 = 2 (2 в остатке)

Определение. Делителем числа а называется число, на которое число а делится без остатка.

Делителем числа 12 называется число, на которое 12 делится без остатка.

Попробуем перечислить эти числа:

Все эти числа являются делителями числа 12, поскольку число 12 делится на них без остатка. Покажем это:

12 : 1 = 12
12 : 2 = 6
12 : 3 = 4
12 : 4 = 3
12 : 6 = 2
12 : 12 = 1

Кратные числа

Если какое-нибудь число без остатка разделилось на другое, то его называют кратным этого числа. Например, 6 без остатка делится на 3. Поэтому 6 является кратным числа 3

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

Кратным числа 5 называется число, которое делится без остатка на 5 .

У любого числа бесконечно много кратных. Например, первыми кратными числа 5, являются числа 5, 10, 15, 20, 25. Все они кратны 5, поскольку делятся на 5 без остатка:

5 : 5 = 1
10 : 5 = 2
15 : 5 = 3
20 : 5 = 4
25 : 5 = 5

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

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

Признак делимости на 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.

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

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

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

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

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

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

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

Чётные и нечётные числа

Чётным называется число, которое делится без остатка на 2. Например, число 20 является четным, поскольку оно делится без остатка на 2:

Нечётным называется число, если при его делении на 2, остаётся остаток 1. Например число 21 является нечетным, поскольку после его деления на 2 остается остаток 1:

21 : 2 = 10 (1 в остатке)

Как распознать чётное число от нечетного, не выполняя деления на 2? Очень просто. Из однозначных чисел чётными являются числа 0, 2, 4, 6, 8, а нечетными являются 1, 3, 5, 7, 9. Если число оканчивается чётной цифрой, то это число является чётным. Если число оканчивается нечетной цифрой, то это число является нечетным.

Например, число 308 чётно, поскольку оно оканчивается чётной цифрой. Число 1024 тоже четно, поскольку оканчивается четной цифрой.

А числа 305 и 1027 являются нечётными, поскольку они оканчиваются нечётными цифрами.

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

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

Значит, число 5 является простым числом.

Составным же называется число, которое имеет два и более делителя. Например, число 4 составное, поскольку у него два и более делителя: 4, 2 и 1

Значит, число 4 является составным числом.

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

Любое составное число можно разложить на простые множители. Чем-то похожим мы занимались в уроке замены в выражениях. Из этого урока мы узнали, что любое число, входящее в выражение, можно заменить на то же самое, но записанное в другом виде.

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

Разложим число 4 на простые множители. Для этого соберем данное число из других чисел, при этом соединим их знаком умножения (×). Число 4 состоит из чисел 2 и 2. Эти два числа и являются простыми множителями, из которых состоит число 4

Разложим на множители число 6. Число 6 можно собрать из чисел 2 и 3. Эти два числа и являются простыми множителями, из которых состоит число 6

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

Например, разложим число 180 на простые множители. Число 180 это два множителя 18 и 10

Теперь раскладываем множители 18 и 10 на другие множители:

Теперь раскладываем выделенную синюю шестерку. Это последний большой множитель, который можно разложить на простые множители:

Теперь собираем все простые множители вместе:

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

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

При разложении числа этим способом, используют признаки делимости, такие как: признаки делимости на 2, на 3, на 5 и другие.

Например, разложим предыдущее число 180 этим способом.

Проводим вертикальную линию и слева записываем первое делимое 180

Теперь применяем признаки делимости. В первую очередь проверяем делится ли 180 на 2. Если делится, то нужно записать эту двойку справа от вертикальной линии.

180 делится на 2, поскольку 180 оканчивается нулём. Записываем двойку справа от вертикальной линии:

Теперь делим 180 на 2 и получаем второе делимое 90. Записываем это делимое слева от вертикальной линии:

Теперь делим 90. Снова применяем признаки делимости. Проверяем делится ли 90 на 2.

90 делится на 2, поскольку 90 оканчивается нулём. Записываем двойку справа от вертикальной линии:

Теперь делим 90 на 2, получаем третье делимое 45. Записываем это делимое слева от вертикальной линии:

Теперь делим 45. Снова применяем признаки делимости. Проверяем делится ли 45 на 2.

45 на 2 не делится. Тогда проверяем делится ли 45 на 3.

45 делится на 3, поскольку сумма цифр 4 и 5 делится на 3. Записываем тройку справа от вертикальной линии:

Делим 45 на 3, получаем четвёртое делимое 15. Записываем это делимое слева от вертикальной линии:

Теперь делим 15. Проверяем делится ли 15 на 2.

15 не делится на 2. Тогда проверяем делится ли 15 на 3.

15 на 3 делится, поскольку сумма цифр 1 и 5 делится на 3. Записываем тройку справа от вертикальной линии:

Делим 15 на 3, получаем пятое делимое 5. Записываем пятёрку слева от вертикальной линии:

Теперь делим 5. Проверяем делится ли 5 на 2.

5 не делится на 2. Тогда проверяем делится ли 5 на 3.

5 не делится на 3. Тогда проверяем делится ли 5 на 5.

5 делится на 5. Записываем эту пятёрку справа от вертикальной линии:

Делим 5 на 5, получаем шестое делимое 1. Записываем эту единицу слева от вертикальной линии:

На этом деление завершается, поскольку мы достигли единицы. Делители, которые записывают справа от вертикальной линии должны быть простыми числами. Поэтому, когда делимое 5 не разделилось на 2, а затем не разделилось на 3, мы попробовали разделить его на 5, не пробуя разделить на 4, поскольку 4 является не простым, а составным числом.

Теперь переписываем в один ряд все делители, которые записаны справа от вертикальной линии. Они и будут разложением числа 180 на простые множители. Желательно записывать их, начиная с самых малых. Это позволяет упорядочить их по возрастанию:

Не расстраивайтесь, если будете испытывать затруднения при разложении чисел на простые множители. Эта тема требует немного практики. Для тренировки можете разложить на простые множители следующие числа: 256, 378, 512.

Нахождение делителей числа

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

Например, число 2 является делителем числа 6, поскольку число 6 можно без остатка разделить на 2

6 : 2 = 3

Ещё делителем числа 6 является число 3

6 : 3 = 2

Ещё делителем числа 6 является число 1

6 : 1 = 6

Наконец, делителем числа 6 является само это число

6 : 6 = 1

Перечислим все делители числа 6

1, 2, 3, 6

Иногда возникает необходимость найти все делители какого-нибудь числа. Чтобы понять, как это делается, рассмотрим несколько примеров.

Пример 1. Найти делители числа 12

Во-первых, единица является делителем любого числа. Пусть и у нас первым делителем числа 12 будет 1

Теперь раскладываем число 12 на простые множители:

Получили разложение 2 × 2 × 3.

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

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

Число 12 мы разложили на простые множители 2 × 2 × 3. Найдём все возможные произведения этих простых множителей между собой. Первое произведение это 2 × 2. Это произведение равно 4

Занесём число 4 в нашу таблицу делителей

Следующее возможное произведение из простых множителей числа 12 это произведение 2 × 3. Данное произведение равно 6. Занесём число 6 в нашу таблицу делителей:

Последнее возможное произведение из простых множителей числа 12 это произведение из всех его множителей, а именно 2 × 2 × 3. Это произведение равно 12. Занесём число 12 в нашу таблицу делителей:

Таким образом, делителями числа 12 являются числа 1, 2, 3, 4, 6, 12.

На основании приведённого примера можно сформировать правило для нахождения делителей числа:

Чтобы найти делители числа, нужно:

Пример 2. Найти делители числа 6

Первым делителем числа 6 запишем единицу:

Теперь разложим число 6 на простые множители:

Выпишем из полученного разложения те множители, которые являются делителями числа 6. Видим, что это множители 2 и 3. Они будут следующими делителями числа 6. Допишем их к нашим делителям:

1, 2, 3

1, 2, 3, 6

Источник

Делитель

Всего получено оценок: 333.

Всего получено оценок: 333.

Операция деления – это основа основ современного мира. Имеется в виду не только математика, но и все точные науки, биология, информатика и экономика. Поговорим об определении делителя числа в операции деления.

Что такое деление?

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

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

Классическая формула деления выглядит так:

с-частное, то есть результат деления.

Самые простые операции деления можно проводить с помощью таблицы умножения. Например, если 3*5=15, то если число 15 поделить на 5 получится 3 и так далее.

Простые и сложные делители

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

Простым числом называют число, которое может делиться только на 1 и на себя. Такими числами являются 2,3, 5 и так далее. Чтобы не ошибиться, лучше использовать таблицу простых чисел. Любое число, которое не является простым, считается составным.

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

Но простые делители нужны, когда число раскладывается на простые множители. Это нужно для того, чтобы определить наибольший общий делитель и наименьшее общее кратное числа. А НОК и НОД в свою очередь нужны для того, чтобы правильно складывать, вычитать и сравнивать дроби.

Правило знаков

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

Что мы узнали?

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

Источник

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

Простое число — это натуральное число имеющие 2 делителя (делится без остатка): единицу и само это число. При этом единица не является ни простым, ни составным числом. К примеру: 2, 3, 5, 7, 11 и т.д — простые числа.

Числа, которые имеют больше двух делителей называют составными. К примеру: 4, 6, 9 и т.д. Таким образом все натуральные числа, за исключением единицы являются либо простыми, либо составными.

Таблица простых чисел до 500

Как определить простое число или нет?

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

Пример: определить 489 простое число или нет?

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

Взаимно простые числа — это числа, которые не имеют общих делителей, кроме единицы. Подробнее про взаимно простые числа смотрите тут

Источник

Разложение числа на простые множители (факторизация). Делители числа

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

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

\[2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots\]

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

Часто это записывается со степенями простых множителей:

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

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

Проверка числа на простоту

Чтобы проверить, является ли натуральное число \(x\) простым, достаточно просто проверить, существует ли в отрезке \([2;\sqrt]\) число, на которое делится \(x\). Это достаточно очевидно: если бы существовало такое число \(y\), что \(x\) делится на \(y\) и \(\sqrt

Сложность этого алгоритма \(O(\sqrt)\). Существуют алгоритмы, позволяющие выполнять эту проверку быстрее (порядка \(O(\log^6 N)\)), но они исключительно редко применяются в спортивном программировании.

Факторизация

Факторизацией называется разложение числа на простые множители. Алгоритм факторизации основывается на тех же идеях, что и алгоритм проверки на простоту, приведённый выше. А именно: если у числа существует простой делитель, отличный от него самого, то он не превышает корня из числа. Для факторизации числа нужно перебрать все числа в промежутке \([2;\sqrt]\), и попытаться разделить \(x\) на каждое из них по очереди.

Реализация на C++ (Сложность: \(O(\sqrt)\)):

Корректность этого алгоритма доказать также несложно. Заметим, что если при факторизации числа \(x\) мы нашли делитель \(y\), то нам, по факту, осталось факторизовать число \(x/y\). Поэтому мы можем смело разделить число \(x\) на \(y\) и продолжить работу алгоритма. Мы можем не начинать проверку сначала, так как число \(x/y\) гарантированно не имеет делителей меньше \(y\), иначе мы бы их уже нашли при факторизации \(x\).

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

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

Поиск делителей

Алгоритм поиска делителей числа \(x\) во многом похож на другие алгоритмы, приведённые выше. Мы рассматриваем делители парами: для каждого делителя \(y\) мы учитываем соответствующий ему \(x/y\). Один из этих делителей гарантированно не превышает \(\sqrt\), поэтому, как и раньше, мы можем рассматривать только промежуток \([1;\sqrt]\).

Реализация на C++ (Сложность: \(O(\sqrt)\)):

Количество делителей

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

Для этого давайте определим понятие делителя в контексте простых множителей. Запишем числа \(x\) и \(y\) в следующем виде:

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

Утверждение: частное двух чисел можно записать следующим образом:

Так как мы работаем с натуральными числами, это выражение имеет смысл тогда и только тогда, когда все степени простых множителей целые и неотрицательные. Отсюда можно выразить условие делимости двух чисел:

\[\forall i: \beta_i \le \alpha_i\]

(Если вы не знакомы с подобной записью, \(\forall i\) обозначает “для всех \(i\)”)

Из этого условия можно легко вывести количество делитей. Ещё раз запишем \(x\) в виде

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

Давайте рассмотрим, сколько возможных значений может принимать каждая степень \(\beta_i\). С ней связано два условия:

\(\beta_i \ge 0\)
\(\beta_i \le \alpha_i\)

Значит, каждая из степеней \(\beta_i\) может принимать \(\alpha_i + 1\) различных значений, и набор степеней \(\beta\) однозначно описывает уникальный делитель. Используя формулы комбинаторики мы можем выразить количество делителей следующим образом:

\[K = (\alpha_1 + 1) * (\alpha_2 + 1) * \ldots * (\alpha_n + 1) = \prod\limits_i (\alpha_i + 1)\]

brestprog

Олимпиадное программирование в Бресте и Беларуси

Источник