Задание 25 ЕГЭ по информатике: решайте с автопроверкой

В задании 25 нужно найти числа из диапазона с особыми делителями: с заданной суммой наименьшего и наибольшего делителя, с ровно k делителями, произведения простых. Другой вид задач: числа по маске с символами * и ?, кратные заданному.

Решать задачи номера

Как решать программой

Делители числа n ищут перебором d до √n: если n делится на d, то делителями будут и d, и n // d. Так проверка одного числа занимает около 30 тысяч шагов даже для миллиарда.

Наименьший нетривиальный делитель — это первое найденное d, а наибольший — это n // d для того же d. Если делителей до √n нет, число простое.

Для масок переберите числа, кратные заданному, и проверьте запись через fnmatch.fnmatch(str(n), маска): * означает любую последовательность цифр, ? одну цифру.

Если в задаче нужно ровно k делителей, считайте их тем же перебором до корня: каждая найденная пара даёт два делителя, а для полного квадрата корень считается один раз.

Разбор примера

M(N) — это сумма наименьшего и наибольшего нетривиальных делителей. Найдём первые пять чисел больше 10, у которых M(N) оканчивается на 8.

def M(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d + n // d
        d += 1
    return None

found = []
n = 10
while len(found) < 5:
    n += 1
    m = M(n)
    if m is not None and m % 10 == 8:
        found.append((n, m))
for n, m in found:
    print(n, m)

Программа печатает

12 8
15 8
32 18
45 18
52 28

Первое число 12: наименьший делитель 2, наибольший 6, сумма 8. Дальше идут 15 (3 + 5), 32 (2 + 16), 45 (3 + 15) и 52 (2 + 26). Простые числа программа пропускает: у них M(N) не определено.

Решить эту задачу

Задачи к заданию 25

  • Сумма крайних делителейСредняяРешать
  • Ровно k делителей на отрезкеСредняяРешать
  • Произведения близких простыхСредняяРешать
  • Сумма простых делителейСредняяРешать
  • Делитель с нужной последней цифройСредняяРешать
  • Наибольший делитель — палиндромСредняяРешать
  • Кратные по маскеСредняяРешать
  • Квадраты по маскеСредняяРешать
  • Простые числа по маскеСредняяРешать
  • Маска с чётной цифрой и сумма цифрСредняяРешать
  • Избыточные числа с кратной суммойСредняяРешать
  • Делятся на сумму цифр по маскеСредняяРешать

Бесплатно и без регистрации: пишете код в браузере и проверяете его тестами (без аккаунта — несколько задач в день).

Вопросы и ответы

Почему перебор до корня?
Делители идут парами d и n / d, и меньший из пары не больше √n. Дальше искать не нужно.
Как проверить число по маске?
Функцией fnmatch из одноимённого модуля. Она понимает * и ? так же, как в условии.
Что если делитель ровно один?
Так бывает у квадрата простого числа, например 49. Этот делитель считается и наименьшим, и наибольшим.