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

Решение:

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

Числа перебираются по убыванию, начиная с 799999. Кратность 17 проверяется как m % 17 == 0, причём нулевое значение по условию кратным не считается, поэтому добавляем проверку $M \ne 0$. Найденные числа выводятся в порядке убывания.

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

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

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

799995 266662
799990 399993
799967 114274
799956 399976
799922 399959

Ответ: 799995 266662 799990 399993 799967 114274 799956 399976 799922 399959