Задание 25 ЕГЭ: делители числа

Делители числа: количество, сумма, наименьший и наибольший. Тема номера — делители и маски чисел. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Пусть M — сумма наименьшего и наибольшего натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.

Напишите программу, которая перебирает целые числа, бо́льшие 857 072, в порядке возрастания и ищет среди них такие, для которых значение M отлично от нуля и кратно 18. Найдите первые 5 таких чисел.

В ответе запишите найденные числа в порядке возрастания, справа от каждого числа — соответствующее значение M. Запишите каждую пару чисел с новой строки, числа — через пробел.

Решение

Наименьший делитель d, больший 1, ищем перебором до корня из n — первый найденный и есть наименьший; тогда наибольший делитель, отличный от n, равен n // d. Если до корня делителей нет, число простое и M = 0.

def min_div(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return d
        d += 1
    return 0          # делителей, кроме 1 и n, нет


def M(n):
    d = min_div(n)
    return d + n // d if d else 0


n = 857072
found = 0
while found < 5:
    n += 1
    m = M(n)
    if m != 0 and m % 18 == 0:
        print(n, m)
        found += 1

Ответ:
857079 285696
857084 428544
857111 14112
857120 428562
857123 50436

Решить такую задачу — новый вариант с проверкой