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

Решение:

Ключевое наблюдение: наименьший делитель числа $n$, не равный 1, — это его наименьший простой делитель $p$, а наибольший делитель, не равный $n$, — это $n/p$. Действительно, если $d$ — делитель, то $n/d$ — тоже делитель, и наименьшему делителю соответствует наибольший. Значит $$F=\frac{n}{p}-p,$$ а если $n$ простое, то «средних» делителей нет и $F=0$.

Поэтому искать $p$ достаточно перебором до $\sqrt{n}$: для $n\approx 850\,000$ это менее 1000 шагов, и вся программа отрабатывает мгновенно.

Перебираем числа, большие 850 000, по возрастанию и выводим первые 6 таких, у которых $F\ne 0$ и $F$ делится на 5.

def F(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d - d
        d += 1
    return 0

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

Проверим пару строк вручную. Для $n=850004$ наименьший простой делитель $p=2$, значит $F=850004/2-2=425002-2=425000$ — делится на 5. Для $n=850025$ имеем $p=5$, $F=170005-5=170000$ — тоже делится на 5. А, например, 850001 в ответ не попало: у него $F$ на 5 не делится. Программа печатает шесть строк:

Число	$F$
850004	425000
850014	425005
850024	425010
850025	170000
850029	283340
850034	425015

Ответ: 850004 425000 850014 425005 850024 425010 850025 170000 850029 283340 850034 425015