Задание №25 — Проверка делимости

Решение:

У целого числа $n$ наименьший делитель, отличный от единицы, — это его наименьший простой делитель $p$. Ему в пару идёт наибольший делитель, отличный от самого числа, равный $n/p$. Значит, оба «крайних» делителя находятся за один проход: достаточно перебрать $d$ от 2 до $\sqrt{n}$ и остановиться на первом, который делит $n$. Если такого $d$ нет, число простое, промежуточных делителей у него нет.

Здесь $M = n/p + p$ — сумма крайних делителей. Условие «оканчивается на 8» касается последней цифры, то есть m % 10 == 8. Перебираем числа, начиная с 700001, по возрастанию и останавливаемся, найдя пять подходящих.

def M(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d + d      # наибольший делитель плюс наименьший
        d += 1
    return 0                       # n простое: делителей нет

n = 700000
found = 0
while found < 5:
    n += 1
    m = M(n)
    if m % 10 == 8:
        print(n, m)
        found += 1

Программа выводит:

700005 233338
700007 100008
700012 350008
700015 140008
700031 24168

Ответ: 700005 233338 700007 100008 700012 350008 700015 140008 700031 24168