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

Решение:

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

Значение $M = n/p - p$ оканчивается на 18 — это условие на две последние цифры, то есть m % 100 == 18. Перебираем числа, начиная с 860001, по возрастанию и останавливаемся, набрав пять подходящих.

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

n = 860000
found = 0
while found < 5:
    n += 1
    m = M(n)
    if m % 100 == 18:      # M оканчивается на 18
        print(n, m)
        found += 1

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

860040 430018
860163 286718
860219 27718
860240 430118
860440 430218

Ответ: 860040 430018 860163 286718 860219 27718 860240 430118 860440 430218