Перебор чисел: делители и сумма M
Задание 25 · Билет 1 · ЕГЭ по информатике
Условие
Пусть — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение признаётся равным нулю.
Напишите программу, которая перебирает целые числа, большие 800000, в порядке возрастания и ищет среди них такие, для которых оканчивается на 4.
Например, для числа 20: .
Обозначения
Пусть — очередное перебираемое число. Пусть — его минимальный собственный делитель (наименьшее , на которое делится без остатка); тогда максимальный делитель равен (поделив на , получаем парный делитель, ведь ), а — сумма минимального и максимального делителей.
Попробуйте программой
Необязательно, но удобно: напишите здесь свой код на Python, который найдёт ответ. Если не получится — откройте решение и вставьте готовую программу одной кнопкой.
Решите программой на Python
в браузереНапишите свой код, который найдёт ответ, и нажмите «Выполнить». Горячая клавиша запуска: Ctrl/⌘ + Enter.
Разбор задачи
Задание 25 ЕГЭ по информатике — перебор чисел и делители. Нужно просматривать числа больше порога в порядке возрастания и находить первые пять таких, у которых значение оканчивается на заданную цифру.
Руками такой перебор не сделать, поэтому пишут короткую программу: для каждого числа находят делители и считают , а первые пять подходящих чисел выводят таблицей с их значениями.
Что важно знать
- Задание высокого уровня — оценивается в 1 балл
- Ответ — таблица: первые пять чисел в порядке возрастания и соответствующие им значения
- У очередного числа минимальный собственный делитель ищут перебором от 2 до , а максимальный равен
План решения
- Перепишите условие: что такое и какой цифрой должно оканчиваться значение.
- У очередного числа найдите минимальный собственный делитель и посчитайте .
- Перебирайте числа больше порога в порядке возрастания и проверяйте последнюю цифру значения.
- Соберите первые пять подходящих чисел и запишите таблицей «число — значение».
Потренируйся перебирать числа: разбери поиск делителей по шагам, а затем напиши программу, которая найдёт первые пять подходящих чисел.
Решение
Теория с нуля: что нужно знать
Мы нашли минимальный собственный делитель : число делится на без остатка, и в частном получается целое число. Обозначим его . Тогда .
То есть — это произведение и , поэтому тоже делит без остатка (). Вот откуда берётся пара: разделив на , мы получили третье число , и оно автоматически тоже делитель, ведь . Значит, делится и на , и на — эти два числа и есть пара делителей.
В каждой паре чем меньше один делитель, тем больше второй (произведение всегда равно ). Поэтому минимальному делителю отвечает максимальный — . Пример: : , ; проверка , поэтому .
Решение
открыто шагов: 6 из 6Программа на Python
# M — сумма минимального и максимального собственных делителей
# (делителей, кроме 1 и самого числа). Если делителей нет, M = 0.
def M_value(n):
d = None
for k in range(2, int(n ** 0.5) + 1): # ищем минимальный делитель
if n % k == 0:
d = k # первый найденный — минимальный
break
if d is None: # простого числа нет в списке
return 0 # собственных делителей нет
return d + n // d # минимальный + максимальный
found = [] # первые пять подходящих чисел
n = 800001 # перебираем числа больше 800000
while len(found) < 5:
M = M_value(n)
if M % 10 == 4: # M оканчивается на 4
found.append((n, M))
n += 1
for x, M in found: # печатаем число и M
print(x, M) | Число | M |
|---|---|
| 800004 | 400004 |
| 800009 | 114294 |
| 800013 | 266674 |
| 800024 | 400014 |
| 800033 | 61554 |
Проверка
Типовые ошибки и проверка
- Учитывают 1 и само число как делители, хотя их исключают.
- Ищут максимальный делитель перебором до — программа работает слишком долго; его берут как .
- Путают условия: « оканчивается на 4» — это последняя цифра , а не делимость.
- Начинают перебор с 800000 включительно, хотя нужно .
- Проверка: для найденных чисел вручную проверьте делители и пересчитайте .
Режимы
Сейчас открыт режим обучения: теория, разбор и ответ видны. Скоро появится режим проверки — только условие и поле ответа, без подсказок.
Практикум Все задания Режим проверки — скоро