к списку статей
Практика оптимального программирования. Поиск делителей числа
На этой странице вы узнаете
- Как быстро работает программа?
- Есть ли смысл перебирать делители после корня?
- Что количество делителей может сказать о самом числе?
Гадание на кофейной гуще или на картах Таро? Может, на ромашке? Хотя лучше не доверять свои отношения цветку. Наша судьба — только в наших руках. А судьба чисел предопределена заранее. Сегодня мы будем предсказывать их жизнь и судьбу по делителям. Но главная проблема — найти эти делители.
Постановка проблемы. Переборное решение
Встречали ли вы странных персонажей в задачах, которым резко понадобилось купить 50 арбузов? А что подумаете, если ваш учитель математики задаст найти число, у которого 50 делителей?
Что такое делители?
Делители числа – это такие числа, на которые число делится без остатка.
Например: число 8 делится без остатка на 1, 2, 4, 8, но если мы попробуем его разделить на 3, у нас получится остаток 2. Поэтому 1, 2, 4, 8 — делители числа 8, а вот 3 не является делителем этого числа.
Нетривиальные делители – это все делители числа, кроме 1 и самого числа.
Например, все у того же числа 8 будет 4 делителя, но только 2 из них будут нетривиальными: 2 и 4.
Также для решения заданий на делители нужно вспомнить, что такое четные и нечетные числа:
Четные числа – числа, которые делятся на 2.
Нечетные числа – числа, которые на 2 не делятся.
Поиск делителей в математике не самый сложный процесс. Есть разные способы: разложение на простые множители, обычный перебор и так далее. Сложность задания будет зависеть от самого числа. Довольно быстро получится найти делители числа 24 — число небольшое, красивое, удобное. Нахождение делителей числа 1234567 займет гораздо больше времени.
Также для решения заданий по поиску делителей нужно знать, что такое интервалы чисел и как их задавать в Python.
Интервал чисел – это последовательность чисел, у которой есть начало и конец, при этом начало и конец входят в данную последовательность.
В Python интервал чисел задается с помощью цикла for. В данном цикле задается начальное и конечное значение, но конечное значение задается не включительно.
Например интервал от 5000 до 10000 в питоне задается таким образом:
for i in range (5000, 10000 + 1) :
Мы прибавляем единицу, чтобы перебор шел четко до 10000.
Нужно отметить, что существует также другой тип таких заданий, когда мы должны найти определенное количество чисел, больших какого-то числа. В таких случаях мы используем циклы while.
Например, чтобы найти 5 чисел, больших 10000, нам нужно написать такой код:
count = 0
n = 10001
while count < 5 :
Давайте включим компьютер, откроем среду разработки и заставим код сделать за нас всю работу.
Идея в следующем:
- Создадим список, в который мы сохраним все делители числа.
- С помощью цикла for переберем все числа из диапазона от 1 до самого числа.
- Если в переборе мы нашли такое число, которое является делителем исходного — остаток от деления будет равен 0 — сохраним это число в список.
В итоге мы получим список всех делителей исходного числа.
number = 1234567
dels = []
for i in range(1, number + 1):
if number % i == 0:
dels.append(i)
print(dels)
Вывод: [1, 127, 9721, 1234567]
У этого метода есть очень большая проблема — время его работы.
Программа выполняет команды очень быстро, но не бесконечно быстро.
| Как быстро работает программа? Время работы программы можно измерить. Например, Sublime Text 3 занимается этим автоматически. При его использовании программа выше выполнилась бы за 0.2 секунды. Давайте постепенно повышать ставки и смотреть, сколько времени понадобится этой же программе для поиска делителей других чисел: — число 1234567 — 0.2 секунды; — число 12345670 — 0.9 секунды; — число 123456700 — 8.0 секунд; — число 1234567000 — 115.7 секунд. С числом 1234567 программа сделала 1234567 шагов цикла for и справилась неимоверно быстро. Но чем больше ей придется выполнять команд, тем дольше придется работать. |
Замеры времени зависят от многих факторов, например, мощности компьютера. Но мы можем повысить эффективность работы программы.
Ускоренный перебор делителей
Идея ускоренного перебора делителей заключается в том, что, найдя один делитель, мы сразу можем подобрать второй — его пару.
Возьмем число 24. Найдя его делитель 2, мы сразу можем сказать, что у 24 есть еще один делитель — 12, потому что 12 = 24 / 2. Интересная мысль? Давайте ее развивать.
Найдем по такой логике все делители числа 16.
- Самый простой делитель числа — 1. И по этой логике сразу найдем второй делитель — само число 16, так как 16 / 1 = 16.
- Проверим число 2. Это делитель, так что сразу найдем его пару: 16 / 2 = 8.
- Проверяем число 3 — это не делитель, его просто пропускаем.
- При проверке числа 4 мы столкнемся с интересной ситуацией. Его парой будет 16 / 4 = 4 — то же самое число, а мы ищем различные пары. Значит, у корня числа пары не будет: найдя корень, мы найдем только один делитель.
Если мы продолжим перебор, числа 5, 6 и 7 не будут делителями. А за ними — 8, делитель, который мы уже нашли.
| Есть ли смысл перебирать делители после корня? Нет. Найдя «маленький» делитель, при ускоренном переборе мы можем найти его пару, которая будет «большим» делителем. Перебирая делители, рано или поздно мы дойдем до корня числа, у которого нет пары. Перебирая числа после корня, мы будем находить только «большие» делители, которые уже нашли в паре с «маленькими». |
Если у числа целого корня нет, перебираем до его округленного вниз значения.
Нам нет смысла перебирать числа после корня, так что будем перебирать до предельно близкого к нему значения, но не больше. В коде лучше всего это сделать с помощью функции int и возведения числа в степень. Это будет выглядеть так:
for i in range(1, int(n ** 0.5) + 1)
Логика программы будет такой:
- Перебираем числа от 1 до корня исходного числа.
- Если мы нашли корень числа, добавляем в список делителей только его.
- Если мы нашли не корень, а обычный делитель — добавляем в список сразу пару делителей.
Пример реализации ускоренного перебора делителей для числа 1234567000:
number = 1234567000
dels = []
for i in range(1, int(number ** 0.5) + 1):
if i * i == number:
dels.append(i)
elif number % i == 0:
dels.append(i)
dels.append(number // i)
print(len(dels))
Вывод: 64
Эта программа нашла все делители числа и выдала их количество — 64. А на ее работу ушло меньше секунды.
Но и это не панацея. Что, если нам придется проверить делители сразу нескольких чисел? Например, мы хотим найти все числа, у которых ровно 7 делителей, в диапазоне от 1 до 10000.
Программу надо немного модифицировать:
- Заведем переменную-счетчик, которая будет считать подходящие числа.
- Number сделаем перебираемой переменной по нужному диапазону с помощью цикла for.
- Ускоренный перебор будет внутри перебора number.
- В конце каждого шага цикла проверяем — если делителей у числа ровно 7, то увеличиваем наш счетчик на 1.
Теперь программа будет выглядеть следующим образом:
count = 0
for number in range(1, 10000):
dels = []
for i in range(1, int(number ** 0.5) + 1):
if i * i == number:
dels.append(i)
elif number % i == 0:
dels.append(i)
dels.append(number // i)
if len(dels) == 7:
count += 1
print(count)
Вывод: 2
Эта программа работала всего 0.2 секунды. Звучит неплохо, но давайте снова поднимать ставки:
- диапазон 1-10000 — 0.2 секунды;
- диапазон 1-100000 — 2.6 секунды;
- диапазон 1-1000000 — 80.2 секунды.
Время снова увеличивается. Что можно с этим сделать?
Не считаем, что не нужно
Обратите внимание — программа выше нашла среди чисел 1–10000 всего 2 числа, имеющих ровно 7 делителей. А сколько же у остальных? Может быть и больше, может быть и меньше. Например, у числа 9864 делителей аж 24 штуки. Стоило ли тратить время на поиск их всех, если количество делителей больше 7?
Конечно, нет. Как только мы нашли 8 штук, мы уже можем понять, что анализировать число далее нам неинтересно. Значит, нужно остановить работу цикла.
Команда break полностью останавливает работу цикла.
Мы можем модернизировать нашу последнюю программу: если в переборе делителей мы увидим, что их больше семи, завершаем цикл командой break.
count = 0
for number in range(1, 10000):
dels = []
for i in range(1, int(number ** 0.5) + 1):
if i * i == number:
dels.append(i)
elif number % i == 0:
dels.append(i)
dels.append(number // i)
if len(dels) > 7:
break
if len(dels) == 7:
count += 1
print(count)
При этом завершится именно цикл перебора делителей i, так как break находится именно в нем, а цикл перебора number продолжит свою работу.
Давайте произведем замеры еще раз:
- диапазон 1-10000 — 0.2 секунды;
- диапазон 1-100000 — 2.1 секунды;
- диапазон 1-1000000 — 53.5 секунды.
В последнем случае мы сэкономили около трети от времени работы программы. Но и это не предел.
Не считаем, что не нужно 2.0
Вернемся на несколько абзацев выше, когда мы искали делители числа 16. Мы нашли 5 делителей — 2 пары и 1 корень, который не даст пару. Это справедливо для любого числа: целый корень не будет давать пару ни с каким другим числом, а все остальные делители — будут.
| Что количество делителей может сказать о числе? Если у числа есть целый корень, количество делителей числа будет нечетным, так как корень не даст пару ни с кем. Поэтому, когда нас просят найти числа с нечетным числом делителей, то можно проверять только числа, у которых есть целый корень. Если же у числа целого корня нет — количество его делителей будет четным, так как все делители будут иметь пару. Соответственно, решая задачу, где нужны числа с четным количеством делителей, мы рассматриваем только числа без целого корня. |
Нам нужны числа, у которых ровно 7 делителей. Следовательно, нам нужны числа, у которых есть целый корень. Мы можем это проверить, вычислив точный корень числа и его округленное значение. Если они совпадут, значит, округлять корень было некуда и он целый.
Но как пропускать числа, которые нам не нужны?
Команда continue останавливает работу текущего шага цикла и сразу переходит к следующему.
Если мы найдем число number, у которого нет целого корня, мы можем применить команду continue: данный шаг цикла перебора number завершается, и мы сразу перейдем к следующему.
Включить эту проверку в программу можно следующим образом:
count = 0
for number in range(1, 10000):
if number ** 0.5 != int(number ** 0.5):
continue
dels = []
for i in range(1, int(number ** 0.5) + 1):
if i * i == number:
dels.append(i)
elif number % i == 0:
dels.append(i)
dels.append(number // i)
if len(dels) > 7:
break
if len(dels) == 7:
count += 1
print(count)
Снова посмотрим на время работы программы при разных диапазонах:
- диапазон 1-100000 — 0.1 секунды;
- диапазон 1-1000000 — 0.5 секунды;
- диапазон 1-10000000 — 4.5 секунды;
- диапазон 1-100000000 — 44.4 секунды.
А делители — это вообще для чего? А таблицы со временем — это точно важно? Может, подождать проще, чем учить все это?
Нахождению делителей чисел посвящена задача 25 ЕГЭ, и без этих теоретических знаний решить ее крайне сложно. Что же касается времени работы, то за ним приходится следить внимательнейшим образом, ведь в задачах могут встречаться ситуации, когда надо найти делители для сотен миллионов чисел за раз!
Давайте потренируемся на реальном номере 25 ЕГЭ:
Задание. Найдите все числа из диапазона [17804; 18500], у которых 8 нетривиальных делителей, и запишите в ответ это число и максимальный нетривиальный делитель.
Решение. Для решения данного задания нужно написать программу.Для начала воспользуемся циклом for, чтобы перебрать все числа из диапазона и создать список всех делителей числа:
for n in range(17804, 18500 + 1):
deliteli = []
Чтобы ускорить перебор, мы проверим числа на отсутствие целого корня:
if n**0.5==int(n**0.5):
continue
Теперь переберем все нетривиальные делители
for i in range(2, int(n ** 0.5) + 1) :
Теперь проверяем все остальные делители, если число делится без остатка, добавляем его и его пару в список делителей:
if n % i == 0:
deliteli.append(i)
deliteli.append(n // i)
Обязательно проверяем, чтобы длина списка делителей не была больше 8:
if len(deliteli) > 8:
break
Последним шагом проверяем, что длина списка делителей равна 8, и выводим число и его максимальный делитель.
if len(deliteli) == 8:
print(n, max(deliteli))
Такой код у нас получился:
for n in range(17804, 18500 + 1):
deliteli = []
if n**0.5==int(n**0.5):
continue
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
deliteli.append(i)
deliteli.append(n // i)
if len(deliteli) > 8:
break
if len(deliteli) == 8:
print(n, max(deliteli))
Данная программа выводит такой ответ:
17872 8936
17968 8984
18063 6021
18064 9032
18125 3625
18387 6129
18416 9208
18448 9224
Зная все особенности ускорения перебора делителей и поиска чисел с конкретными делителями, за считанные секунды мы можем решать задачи огромных диапазонов.
Рассмотрим еще одну задачу 25 из ЕГЭ.
Задание. Найдите 3 первых числа, больших 25000, у которых 5 делителей. Выведите эти числа.
Решение. Здесь для перебора нам лучше использовать цикл while.Заводим переменную count и перебираем числа от 25001:
count = 0
n = 25001
while count < 3:
Создаем список делителей, перебираем все делители с помощью for:
deliteli = []
for i in range(1, int(n ** 0.5) + 1):
Теперь находим все делители числа:
if i * i == n:
deliteli.append(i)
elif n % i == 0:
deliteli.append(i)
deliteli.append(n // i)
Проверяем длину списка делителей
if len(deliteli) > 5:
brea
kif len (deliteli) == 5:
print(n)
count += 1
Осталось только добавить 1 к n, чтобы начать проверять следующее число:
n += 1
Такой код у нас получился:
count = 0
n = 25001
while count < 3:
deliteli = []
for i in range(1, int(n ** 0.5) + 1):
if i * i == n:
deliteli.append(i)
elif n % i == 0:
deliteli.append(i)
deliteli.append(n // i)
if len(deliteli) > 5:
break
if len (deliteli) == 5:
print(n)
count += 1
n += 1
Данная программа выводит такой ответ:2856183521130321
Сегодня мы разобрались с тем, как быстро, а главное правильно решать задачи с поиском делителей. С помощью способов, указанных в этой статье, вы сможете намного быстрее решать задания с перебором чисел. Здесь мы снова убедились, что программирование невероятно облегчает нам жизнь, поэтому мы советуем изучить также статью «Основы программирования. Массивы».
Термины
Множитель – это число, на которое делится данное без остатка.
Фактчек
- Делители числа – это числа, на которые это число делится без остатка.
- Существует понятие «нетривиальный делитель». Это такой делитель, который не равен 1 и самому числу.
- Ускоренный перебор делителей подразумевает нахождение делителей попарно, при этом перебирать делители достаточно только до корня числа.
- Команда break полностью останавливает работу цикла, а команда continue завершает работу лишь текущего шага цикла, перенося нас сразу на следующий.
- Если у числа есть целый корень, количество делителей числа будет нечетным, так как корень не даст пару ни с кем. Если же у числа целого корня нет — количество его делителей будет четным, так как все делители будут иметь пару. Этот факт помогает нам еще быстрее перебирать все числа.
- Когда в задании просят найти числа с четным числом делителей, мы можем перебирать только числа, которые не имеют целого корня, а где нужны числа с нечетным количеством делителей — только числа с целым корнем.
Проверь себя
Задание 1.
Для чего нужен ускоренный перебор делителей?
- Обычный перебор слишком скучный.
- Для большей точности вычислений.
- Для ускорения работы программы.
- Программа получается красивее.
Задание 2.
Найдите количество делителей числа 2568568668.
- 20
- 24
- 22
- 30
Задание 3.
Найдите, сколько чисел из диапазона от 2000 до 1002000 имеют ровно 5 делителей.
- ни одного
- 1
- 10
- 8
Задание 4.
Сколько нетривиальных делителей у числа 26964?
- 34
- 36
- 32
- 40
Ответы: 1. — 3; 2. — 2; 3. — 4; 4. — 1.
