Автор: Андрей Роженцов
Введение
В предыдущей статье (ссылка на статью 34) мы разбирали методы решения задач на маски. Пора перейти ко второму типу задания № 25 — задачам на определение количества делителей числа.
Делитель — натуральное число, на которое заданное число делится нацело, без остатка. Поскольку в подобных задачах постоянно требуется находить делители, логично будет оформить этот алгоритм в виде отдельной функции, которую мы и рассмотрим в первую очередь. Детальный разбор написания функций есть здесь.
Поиск делителей
Самый простой подход — перебрать в цикле все целые числа от 1 до исходного числа (включительно) и проверять делимость каждого. Если остаток от деления равен нулю, то число — делитель, и мы добавляем его в список. Таким образом, функция будет принимать число, а возвращать список всех его делителей.
def F(x):
# Будем добавлять в список делители
divisors = []
# Цикл до самого числа включительно
for i in range(1, x + 1):
if x % i == 0:
# Добавляем делитель i в список
divisors.append(i)
return divisors
Пример вызова функции:
print(F(100)) # [1, 2, 4, 5, 10, 20, 25, 50, 100]
Функция работает корректно, но не самым эффективным образом, так как количество итераций цикла прямо зависит от величины числа x. Чем больше число, тем дольше выполняется поиск. Попробуем оптимизировать алгоритм, сократив количество необходимых проверок.
Давайте внимательно посмотрим на делители числа 100.
Можно заметить, что делители удобно группировать в пары, произведение которых даёт исходное число. Для 100 это пары 1 и 100, 2 и 50, 4 и 25, 5 и 20. Это свойство очень полезно: зная один делитель из пары, мы можем найти второй, просто разделив исходное число на известный делитель.
Без пары остался делитель 10, так как он пара самому себе. Поскольку 10 × 10 = 100, делитель равен квадратному корню из числа.
Из этого наблюдения следует важный вывод: не обязательно перебирать все числа до х, чтобы найти все делители, достаточно тех, что меньше корня из числа. Каждый найденный малый делитель i сразу даёт нам соответствующий большой делитель x // i.
Этот метод сокращает количество операций, особенно для больших чисел, и считается стандартным для решения экзаменационных задач.
Цикл теперь будет идти до корня из числа включительно. Не из каждого числа извлекается корень, поэтому дробную часть будем отбрасывать функцией int().
for i in range(1, int(x ** 0.5) + 1):
При нахождении «маленького» делителя, не забываем также добавить в массив его пару.
divisors.append(i)
divisors.append(x // i)
Для чисел, которые называют точными квадратами (как, например, число 100, корень из которого равен 10), возникает особая ситуация: делитель, равный корню (в нашем случае 10), будет парой самому себе. Если просто добавлять оба числа описанным способом, то число 10 окажется в списке дважды.
Чтобы избежать дублирования, после формирования списка будем преобразовывать его во множество set, которое автоматически удалит все повторяющиеся элементы, а затем снова преобразуем в список list. Для удобства дальнейшего использования итоговый список отсортируем.
return sorted(list(set(divisors)))
Общий вид функции:
def F(x):
# Будем добавлять делители в массив
divisors = []
# Цикл до корня из числа
for i in range(1, int(x ** 0.5) + 1):
if x % i == 0:
# Добавляем делитель i в массив
divisors.append(i)
# Добавляем второй, парный делитель
divisors.append(x // i)
return sorted(list(set(divisors)))
Применение оптимизированного алгоритма даёт существенное преимущество в производительности, особенно при работе с большими числами. Например, для числа 1 000 000 полный перебор охватывает миллион значений, тогда как усовершенствованный подход с перебором до квадратного корня выполнит всего 1000 итераций, а это в 1000 раз быстрее.
Задача 1: простой перебор
Для поиска делителей будем пользоваться оптимизированной функцией. Она найдёт все делители, а по условию задачи нам нужно 2, не считая единицы и самого числа. Получается, что всего 4 делителя.
Выводить будем элементы массива делителей с индексами 1 и 2, т. к. на нулевой позиции стоит единица, а на третьей — само число (функция возвращает отсортированный по возрастанию массив).
def F(x):
divisors = []
for i in range(1, int(x ** 0.5) + 1):
if x % i == 0:
divisors.append(i)
divisors.append(x // i)
return sorted(list(set(divisors)))
for x in range(174457, 174506):
# Находим делители числа
divisors = F(x)
# проверяем количество делителей
if len(divisors) == 4:
print(divisors[1], divisors[2])
Вывод:
3 58153
7 24923
59 2957
13 13421
149 1171
5 34897
211 827
2 87251
Произведение этих делителей и есть исходное число х, а поскольку числа в цикле перебирались в порядке возрастания, ответ мы записываем в такой же последовательности.
Задача 2: извлекается ли корень?
Немного преобразуем функцию для поиска делителей: будем запускать цикл, начиная с 2. Таким образом, делитель 1 и парный к нему (исходное число) не будут попадать в результат. Это значит, что теперь функция находит все делители, не считая единицу и само число.
for i in range(2, int(x ** 0.5) + 1):
Мы знаем, что все делители числа идут парами, кроме одного — корня из этого числа. Значит, если у числа нечётное количество делителей, из него извлекается корень
len(F(d)) % 2 != 0:
Существует ещё один способ это проверить: if (int(d ** 0.5) * int(d ** 0.5)) == d:.
Мы берём корень из числа, округляем полученное значение и умножаем на такой же множитель. Если получилось исходное число, то корень извлекается.
x = 100
print(x ** 0.5) # 10.0
print(int(x ** 0.5)) # 10
print(int(x ** 0.5) * int(x ** 0.5)) # 100
# Сошлось, значит, корень извлекается
x = 79
print(x ** 0.5) # 8.888194417315589
print(int(x ** 0.5)) # 8
print(int(x ** 0.5) * int(x ** 0.5)) # 64
# Не сходится: 79!=64, значит, корень из 79 не извлекается
Перебирать числа будем до тех пор, пока не найдём 5 интересных чисел.
while count < 5:
Не забываем увеличивать число x в цикле!
Если из делителя извлекается корень, то будем запоминать его в переменную max_d. Поскольку числа перебираются в порядке возрастания, последнее, записанное в переменную, и будет максимальным.
Код программы:
def F(x):
# Будем добавлять делители в массив
divisors = []
# Цикл до корня из числа
for i in range(2, int(x ** 0.5) + 1):
if x % i == 0:
# Добавляем делитель i в массив
divisors.append(i)
# Добавляем второй, парный делитель
divisors.append(x // i)
return sorted(list(set(divisors)))
# Счётчик для найденных подходящих чисел
count = 0
# Наименьшее подходящее число
x = 10 ** 7 + 1
while count < 5:
# Получаем массив делителей
divisors = F(x)
# Счётчик количества делителей, из которых извлекается корень
count_squares = 0
# Перебираем все делители числа х
for d in divisors:
# Проверяем, извлекается ли корень
if (int(d ** 0.5) * int(d ** 0.5)) == d:
count_squares += 1
max_d = d
# Проверяем количество делителей, из которых извлекается корень
if count_squares == 3:
print(x, max_d)
# Увеличиваем счётчик подходящих чисел
count += 1
# Увеличиваем x
x += 1
Вывод:
10000008 36
10000040 11236
10000044 36
10000064 64
10000068 676
Задача 3: простые числа
Простое число — это число, которое делится только на 1 и на само себя. Преобразуем функцию для поиска делителей: будем запускать цикл начиная с 2.
for i in range(2, int(x ** 0.5) + 1):
Программа будет выполняться до тех пор, пока мы не найдём пять чисел. Воспользуемся циклом while:
while count < 5:
Не забываем увеличивать число x в цикле!
Для каждого числа будем получать список его делителей. По условию их должно быть 2 или 1 («не обязательно различных»), т. е. из числа можно только извлечь корень.
Циклом перебираем все делители, и если хоть один не подходит хотя бы по одному условию, то делаем flag = False. Проверяем длину списка делителей для самого делителя, она не должна быть равна нулю: len(F(d)) != 0.
Количество цифр 5 в числе проверим методом count('5'), предварительно переведя число в строку: str(d).count('5') != 1.
Код всей программы:
def F(x):
# Будем добавлять делители в массив
divisors = []
# Цикл до корня из числа
for i in range(2, int(x ** 0.5) + 1):
if x % i == 0:
# Добавляем делитель i в массив
divisors.append(i)
# Добавляем второй, парный делитель
divisors.append(x // i)
return sorted(list(set(divisors)))
# Счётчик для найденных подходящих чисел
count = 0
# Наименьшее подходящее число
x = 1324728
while count < 5:
# Получаем массив делителей
divisors = F(x)
# Проверяем, два делителя у числа или один
if 1 <= len(divisors) <= 2:
# Предполагаем, что х подходит
flag = True
# Перебираем его делители
for d in divisors:
# Если хотя бы один не подходит по одному условию, то число x не подходит, flag = False
if len(F(d)) != 0 or str(d).count('5') != 1:
flag = False
# Если переменная flag осталась True, то х подходит
if flag:
# Наибольший делитель находится на последней позиции в списке, т. к. функция F() возвращает его отсортированным
print(x, divisors[-1])
# Увеличиваем счётчик найденных чисел
count += 1
x += 1
Вывод
При решении задач на делители важно опираться на несколько принципов:
- Оптимизация через корень\
Не перебирайте все числа до x, это слишком долго. Достаточно дойти до квадратного корня, сразу найдя пару делителей. Это в разы ускоряет решение, особенно при работе с большими числами. - Аккуратность с точными квадратами\
Если число — полный квадрат, его корень окажется в списке делителей дважды. Используйте множествоset, чтобы убрать дубликаты, и не забывайте сортировать итоговый список для удобства. - Внимание к условиям\
В разных задачах могут требоваться разные наборы делителей — все, кроме единицы и самого числа, или только те, что обладают особыми свойствами (например, извлекается корень или делитель — простое число). Подстраивайте диапазон цикла и проверки к конкретному условию. - Перебор всех вариантов\
Если в задаче нужно найти несколько чисел, удовлетворяющих условию, удобно использовать цикл while со счётчиком найденных. Не забывайте вручную увеличивать проверяемое число, иначе цикл будет работать бесконечно.
Потренироваться и закрепить свои знания можно с помощью подборки заданий.