Задача «Минимальный простой делитель»
Только начал изучать Python на платформе Сириус. Смог решить все остальные задачи из темы «while», кроме одной задачи, которая мне не позволяет пройти на следующие темы. Задача «Минимальный простой делитель числа».
Условие: Дано целое число, не меньшее 2. Выведите его наименьший простой делитель. Нельзя использовать дополнительные библиотеки (math и т.п.)!
Входные данные: Вводится целое положительное число N <= 2*10 в 9-ой степени.
Выходные данные: Выведите ответ на задачу.
Пытался решить, написав код с while, но мой ответ не засчитывается, по причине слишком долгого времени работы программы. Рекомендуют организовать цикл, перебирающий делители до корня из числа N: while i*i <= N: , но я не могу понять, как это сделать.
Мой код Python (выдаёт ошибку «Программа выполнялась слишком долго и была прервана» либо «Программа выдаёт ошибку в процессе выполнения»):
Делимость натуральных чисел.
Деление – это действие, обратное умножению. Рассмотрим более подробно деление натуральных чисел.
Натуральными числами называют числа, используемые для счета. Каждому количеству предметов счета соответствует некоторое натуральное число. Если предметов для счета нет, то используется число 0, но при счете предметов мы никогда не начинают с 0, и соответственно число 0 нельзя отнести к натуральным. Понятно, что наименьшим натуральное число является единица. Наибольшего натурального числа не существует, потому что каким бы большим не было число, всегда можно прибавить к нему 1 и записать следующее натуральное число.
Разберем простейший пример деления: разделим число 30 на число 5 (остаток при делении числа 30 на число 5 равен 0), по сколку 30 = 5 • 6. Значит число 30 делится нацело на число 5. Число 5 — делитель числа 30, а число 30 — кратно числу 5.
Натуральное число k делится нацело на натуральное число n, если найдётся такое натуральное число m, для которого справедливо равенство k =n • m.
Или другими словами, чтобы разделить одно число на другое, надо найти такое трете число, которое при умножении на второе дает первое
Если натуральное число k делится нацело на натуральное число n, то число k называют кратным числа ,
число n — делителем числа k.
Числа 1, 2, 3, 6, 10, 15, 30 также являются делителями числа 30, а число 30 является кратным каждого из этих чисел. Заметим, что число 30 не делится нацело, например, на число 7. Поэтому число 7 не является делителем числа 30, а число 30 не кратно числу 7.
Выполнив действия по делению говорят: «Число k делится нацело на число n», «Число n является делителем числа k», «Число k кратно числу n», «Число k является кратным числа n».
Легко записать все делители числа 6. Это числа 1, 2, 3 и 6. А можно ли перечислить все числа, кратные числу 6? Числа 6• 1, 6• 2, 6• 3, 6• 4, 6• 5 и т. д. кратны числу 6. Получаем, что чисел, кратных числу 6, — бесконечно много. Поэтому перечислить их все невозможно.
Вообще, для любого натурального числа k каждое из чисел
является кратным числа k.
Наименьшим делителем любого натурального числа k является число 1, а наибольшим делителем — само число k.
Среди чисел, кратных числу k, наибольшего нет, а наименьшее есть — это само число k.
Каждое из чисел 21 и 36 делится нацело на число 3, и их сумма, число 57, также делится нацело на число 3. Вообще, если каждое из чисел k и n делится нацело на число m, то и сумма k + n также делится нацело на число m.
Каждое из чисел 4 и 8 не делится нацело на число 3, а их сумма, число 12, делится нацело на число 3. Каждое из чисел 9 и 7 не делится нацело на число 5, и их сумма, число 16, не делится нацело на число 5. Вообще, если ни число k, ни число n не делятся нацело на число m, то сумма k + n может делиться, а может и не делиться нацело на число m.
Число 35 делится без остатка на число 7, а число 17 на число 7 нацело не делится. Сумма 35 + 17 нацело на число 7 также не делится. Вообще, если число k делится нацело на число m и число n не делится нацело на число m, то сумма k + n не делится нацело на число m.
Нахождение всех делителей числа, число делителей числа
В данной статье мы поговорим о том, как найти все делители числа. Начнем с доказательства теоремы, с помощью которой можно задать вид всех делителей определенного числа. Далее возьмем примеры нахождения всех нужных делителей и покажем, как именно определить, сколько делителей имеет конкретное число. В последнем пункте подробно рассмотрим примеры задач на нахождение общих делителей нескольких чисел.
Как найти все делители числа
Чтобы понять материал, изложенный в данном пункте, нужно хорошо знать, что вообще из себя представляют кратные числа и делители. Здесь мы поговорим только о поиске делителей натуральных чисел, т.е. целых положительных. Этим можно ограничиться, поскольку свойство делимости гласит, что делители целого отрицательного числа аналогичны делителям целого положительного, которое будет противоположным по отношению к этому числу. Также сразу уточним, что у нуля есть бесконечно большое число делителей, и находить их смысла не имеет, поскольку в итоге все равно получится 0 .
Если речь идет о простом числе, то его можно разделить только на единицу и на само себя. Значит, у любого простого числа a есть всего 4 делителя, два из которых больше 0 и два меньше: 1 , — 1 , a , — a . Возьмем простое число 7 : у него есть делители 7 , — 7 , 1 и — 1 , и все. Еще один пример: 367 – тоже простое число, которое можно разделить лишь на 1 , — 1 , 367 и — 367 .
Сложнее определить все делители составного числа. Сформулируем теорему, которая лежит в основе данного действия.
Допустим, у нас есть выражение, означающее каноническое разложение числа на простые множители, вида a = p 1 s 1 · p 2 s 2 · … · p n s n . Тогда натуральными делителями числа a будут следующие числа: d = p 1 t 2 · p 2 t 2 · … · p n t n , где t 1 = 0 , 1 , … , s 1 , t 2 = 0 , 1 , … , s 2 , … , t n = 0 , 1 , … , s n .
Перейдем к доказательству этой теоремы. Зная основное определение делимости, мы можем утверждать, что a можно разделить на d , если есть такое число q , что делает верным равенство a = d · q , т.е. q = p 1 ( s 1 − t 1 ) · p 2 ( s 2 — t 2 ) · … · p n ( s n — t n ) .
Любое число, делящее a , будет иметь именно такой вид, поскольку, согласно свойствам делимости, других простых множителей, кроме p 1 , p 2 , … , p n , оно иметь не может, а их показатели в данном случае не превысят s 1 , s 2 , … , s n .
Учитывая доказательство этой теоремы, мы можем сформировать схему нахождения всех положительных делителей данного числа.
Для этого нужно выполнить следующие действия:
- Выполнить каноническое разложение на простые множители и получить выражение вида a = p 1 s 1 · p 2 s 2 · … · p n s n .
- Найти все значения d = p 1 t 2 · p 2 t 2 · … · p n t n , где числа t 1 , t 2 , … , t n будут принимать независимо друг от друга каждое из значений t 1 = 0 , 1 , … , s 1 , t 2 = 0 , 1 , … , s 2 , … , t n = 0 , 1 , … , s n .
Самым трудным в таком расчете является именно перебор всех комбинаций указанных значений. Разберем подробно решения нескольких задач, чтобы наглядно показать применение данной схемы на практике.
Условие: найти все делители 8 .
Решение
Разложим восьмерку на простые множители и получим 8 = 2 · 2 · 2 . Переведем разложение в каноническую форму и получим 8 = 2 3 . Следовательно, a = 8 , p 1 = 2 , s 1 = 3 .
Поскольку все делители восьмерки будут значениями p 1 t 1 = 2 t 1 , то t 1 может принять значения нуля, единицы, двойки, тройки. 3 будет последним значением, ведь s 1 = 3 . Таким образом, если t 1 = 0 , то 2 t 1 = 2 0 = 1 , если 1 , то 2 t 1 = 2 1 = 2 , если 2 , то 2 t 1 = 2 2 = 4 , а если 3 , то 2 t 1 = 2 3 = 8 .
Для нахождения делителей удобно все полученные значения оформлять в виде таблицы:
| t 1 | 2 t 1 |
| 0 | 2 0 = 1 |
| 1 | 2 1 = 2 |
| 2 | 2 2 = 4 |
| 3 | 2 3 = 8 |
Значит, положительными делителями восьмерки будут числа 1 , 2 , 4 и 8 , а отрицательными − 1 , − 2 , − 4 и − 8 .
Ответ: делителями данного числа будут ± 1 , ± 2 , ± 4 , ± 8 .
Возьмем пример чуть сложнее: в нем при разложении числа получится не один, а два множителя.
Условие: найдите все делители числа 567 , являющиеся натуральными числами.
Решение
Начнем с разложения данного числа на простые множители.
567 189 63 21 7 1 3 3 3 3 7
Приведем разложение к каноническому виду и получим 567 = 3 4 · 7 . Затем перейдем к вычислению всех натуральных множителей. Для этого будем присваивать t 1 и t 2 значения 0 , 1 , 2 , 3 , 4 и 0 , 1 , вычисляя при этом значения 3 t 1 · 7 t 2 . Результаты будем вносить в таблицу:
| t 1 | t 2 | 3 t 1 · 7 t 2 |
| 0 | 0 | 3 0 · 7 0 = 1 |
| 0 | 1 | 3 0 · 7 1 = 7 |
| 1 | 0 | 3 1 · 7 0 = 3 |
| 1 | 1 | 3 1 · 7 1 = 21 |
| 2 | 0 | 3 2 · 7 0 = 9 |
| 2 | 1 | 3 2 · 7 1 = 63 |
| 3 | 0 | 3 3 · 7 0 = 27 |
| 3 | 1 | 3 3 · 7 1 = 189 |
| 4 | 0 | 3 4 · 7 0 = 81 |
| 4 | 1 | 3 4 · 7 1 = 567 |
Ответ: натуральными делителями 567 будут числа 27 , 63 , 81 , 189 , 1 , 3 , 7 , 9 , 21 и 567 .
Продолжим усложнять наши примеры – возьмем четырехзначное число.
Условие: найти все делители 3 900 , которые будут больше 0 .
Решение
Проводим разложение данного числа на простые множители. В каноническом виде оно будет выглядеть как 3 900 = 22 · 3 · 52 · 13 . Теперь приступаем к нахождению положительных делителей, подставляя в выражение 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4 значения t 1 , равные 0 , 1 и 2 , t 2 = 0 , 1 , t 3 = 0 , 1 , 2 , t 4 = 0 , 1 . Результаты представляем в табличном виде:
| t 1 | t 2 | t 3 | t 4 | 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4 |
| 0 | 0 | 0 | 0 | 2 0 · 3 0 · 5 0 · 13 0 = 1 |
| 0 | 0 | 0 | 1 | 2 0 · 3 0 · 5 0 · 13 1 = 13 |
| 0 | 0 | 1 | 0 | 2 0 · 3 0 · 5 1 · 13 0 = 5 |
| 0 | 0 | 1 | 1 | 2 0 · 3 0 · 5 1 · 13 1 = 65 |
| 0 | 0 | 2 | 0 | 2 0 · 3 0 · 5 2 · 13 0 = 25 |
| 0 | 0 | 2 | 1 | 2 0 · 3 0 · 5 2 · 13 1 = 325 |
| 0 | 1 | 0 | 0 | 2 0 · 3 1 · 5 0 · 13 0 = 3 |
| 0 | 1 | 0 | 1 | 2 0 · 3 1 · 5 0 · 13 1 = 39 |
| 0 | 1 | 1 | 0 | 2 0 · 3 1 · 5 1 · 13 0 = 15 |
| 0 | 1 | 1 | 1 | 2 0 · 3 1 · 5 1 · 13 1 = 195 |
| 0 | 1 | 2 | 0 | 2 0 · 3 1 · 5 2 · 13 0 = 75 |
| 0 | 1 | 2 | 1 | 2 0 · 3 1 · 5 2 · 13 1 = 975 |
| t 1 | t 2 | t 3 | t 4 | 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4 |
| 1 | 0 | 0 | 0 | 2 1 · 3 0 · 5 0 · 13 0 = 2 |
| 1 | 0 | 0 | 1 | 2 1 · 3 0 · 5 0 · 13 1 = 26 |
| 1 | 0 | 1 | 0 | 2 1 · 3 0 · 5 1 · 13 0 = 10 |
| 1 | 0 | 1 | 1 | 2 1 · 3 0 · 5 1 · 13 1 = 130 |
| 1 | 0 | 2 | 0 | 2 1 · 3 0 · 5 2 · 13 0 = 50 |
| 1 | 0 | 2 | 1 | 2 1 · 3 0 · 5 2 · 13 1 = 650 |
| 1 | 1 | 0 | 0 | 2 1 · 3 1 · 5 0 · 13 0 = 6 |
| 1 | 1 | 0 | 1 | 2 1 · 3 1 · 5 0 · 13 1 = 78 |
| 1 | 1 | 1 | 0 | 2 1 · 3 1 · 5 1 · 13 0 = 30 |
| 1 | 1 | 1 | 1 | 2 1 · 3 1 · 5 1 · 13 1 = 390 |
| 1 | 1 | 2 | 0 | 2 1 · 3 1 · 5 2 · 13 0 = 150 |
| 1 | 1 | 2 | 1 | 2 1 · 3 1 · 5 2 · 13 1 = 1950 |
| t 1 | t 2 | t 3 | t 4 | 2 t 1 · 3 t 2 · 5 t 3 · 13 t 4 |
| 2 | 0 | 0 | 0 | 2 2 · 3 0 · 5 0 · 13 0 = 4 |
| 2 | 0 | 0 | 1 | 2 2 · 3 0 · 5 0 · 13 1 = 52 |
| 2 | 0 | 1 | 0 | 2 2 · 3 0 · 5 1 · 13 0 = 20 |
| 2 | 0 | 1 | 1 | 2 2 · 3 0 · 5 1 · 13 1 = 260 |
| 2 | 0 | 2 | 0 | 2 2 · 3 0 · 5 2 · 13 0 = 100 |
| 2 | 1 | 0 | 1 | 2 2 · 3 0 · 5 2 · 13 1 = 1300 |
| 2 | 1 | 0 | 0 | 2 2 · 3 1 · 5 0 · 13 0 = 12 |
| 2 | 1 | 0 | 1 | 2 2 · 3 1 · 5 0 · 13 1 = 156 |
| 2 | 1 | 1 | 0 | 2 2 · 3 1 · 5 1 · 13 0 = 60 |
| 2 | 1 | 1 | 1 | 2 2 · 3 1 · 5 1 · 13 1 = 780 |
| 2 | 1 | 2 | 0 | 2 2 · 3 1 · 5 2 · 13 0 = 300 |
| 2 | 1 | 2 | 1 | 2 2 · 3 1 · 5 2 · 13 1 = 3900 |
Ответ: делителями числа 3 900 будут: 195 , 260 , 300 , 325 , 390 , 650 , 780 , 975 , 75 , 78 , 100 , 130 , 150 , 156 , 13 , 15 , 20 , 25 , 26 , 30 , 39 , 50 , 52 , 60 , 65 , 1 , 2 , 3 , 4 , 5 , 6 , 10 , 12 , 1 300 , 1 950 , 3 900
Как определить количество делителей конкретного числа
Чтобы узнать, сколько положительных делителей у конкретного числа a, каноническое разложение которого выглядит как a = p 1 s 1 · p 2 s 2 · … · p n s n , нужно найти значение выражения ( s 1 + 1 ) · ( s 2 + 1 ) · … · ( s n + 1 ) . О количестве наборов переменных t 1 , t 2 , … , t n мы можем судить по величине записанного выражения.
Покажем на примере, как это вычисляется. Определим, сколько будет натуральных делителей у числа 3 900 , которое мы использовали в предыдущей задаче. Каноническое разложение мы уже записывали: 3 900 = 2 2 · 3 · 5 2 · 13 . Значит, s 1 = 2 , s 2 = 1 , s 3 = 2 , s 4 = 1 . Теперь подставим значения s 1 , s 2 , s 3 и s 4 в выражение ( s 1 + 1 ) · ( s 2 + 1 ) · ( s 3 + 1 ) · ( s 4 + 1 ) и вычислим его значение. Имеем ( 2 + 1 ) · ( 1 + 1 ) · ( 2 + 1 ) · ( 1 + 1 ) = 3 · 2 · 3 · 2 = 36 . Значит, это число имеет всего 36 делителей, являющихся натуральными числами. Пересчитаем то количество, что у нас получилось в предыдущей задаче, и убедимся в правильности решения. Если учесть и отрицательные делители, которых столько же, сколько и положительных, то получится, что у данного числа всего будет 72 делителя.
Условие: определите, сколько делителей имеет 84 .
Решение
Раскладываем число на множители.
84 42 21 7 1 2 2 3 7
Записываем каноническое разложение: 84 = 2 2 · 3 · 7 . Определяем, сколько у нас получится положительных делителей: ( 2 + 1 ) · ( 1 + 1 ) · ( 1 + 1 ) = 12 . Для учета отрицательных нужно умножить это число на 2 : 2 · 12 = 24 .
Ответ: всего у 84 будет 24 делителя – 12 положительных и 12 отрицательных.
Как вычислить общие делители нескольких чисел
Зная свойства наибольшего общего делителя, можно утверждать, что количество делителей некоторого набора целых чисел будет совпадать с количеством делителей НОД тех же чисел. Это будет справедливо не только для двух чисел, но и для большего их количества. Следовательно, чтобы вычислить все общие делители нескольких чисел, надо определить их наибольший общий множитель и найти все его делители.
Разберем пару таких задач.
Условие: сколько будет натуральных общих делителей у чисел 140 и 50 ? Вычислите их все.
Решение
Начнем с вычисления НОД ( 140 , 50 ) .
Для этого нам потребуется алгоритм Евклида:
140 = 50 · 2 + 40 , 50 = 40 · 1 + 10 , 40 = 10 · 4 , значит, НОД ( 50 , 140 ) = 10 .
Далее выясним, сколько положительных делителей есть у десяти. Разложим его на простые множители и получим 2 0 · 5 0 = 1 , 2 0 · 5 1 = 5 , 2 1 · 5 0 = 2 и 2 1 · 5 1 = 1 0 . Значит, все натуральные общие делители исходного числа – это 1 , 2 , 5 и 10 , а всего их четыре.
Ответ: данные числа имеют четыре натуральных делителя, равные 10 , 5 , 2 и 1 .
Условие: выясните, сколько общих положительных делителей есть у чисел 585 , 315 , 90 и 45 .
Решение
Вычислим их наибольший общий делитель, разложив число на простые множители. Поскольку 90 = 2 · 3 · 3 · 5 , 45 = 3 · 3 · 5 , 315 = 3 · 3 · 5 · 7 и 585 = 3 · 3 · 5 · 13 , то таким делителем будет 5 : НОД ( 90 , 45 , 315 , 585 ) = 3 · 3 · 5 = 3 2 · 5 .
Чтобы узнать количество этих чисел, нужно выяснить, сколько положительных делителей имеет НОД.