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

Решение:

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

Нужны числа, у которых $F = n/p - p$ отлично от нуля и делится нацело на 13. Проверка $F \ne 0$ отсекает простые числа и полные квадраты простых, у которых наибольший и наименьший промежуточные делители совпадают. Перебираем числа с 850001 по возрастанию, пока не наберём шесть.

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

n = 850000
found = 0
while found < 6:
    n += 1
    f = M(n)
    if f != 0 and f % 13 == 0:
        print(n, f)
        found += 1

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

850022 425009
850048 425022
850053 283348
850074 425035
850099 7410
850100 425048

Ответ: 850022 425009 850048 425022 850053 283348 850074 425035 850099 7410 850100 425048