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

Решение:

Наибольший делитель числа $n$, не равный самому $n$, — это $n/p$, где $p$ — наименьший простой делитель $n$. Поэтому достаточно найти $p$ перебором $d$ от 2 до $\sqrt{n}$, а затем проверить, простое ли частное $n/p$.

Простые числа сразу отбрасываем: по условию для них такого делителя не существует. Заметим, что оставшееся условие равносильно тому, что число $n$ раскладывается минимум на три простых множителя с учётом кратности: если множителей всего два, то $n = p\cdot q$ и частное $n/p = q$ простое.

def is_prime(x):
    if x < 2:
        return False
    d = 2
    while d * d <= x:
        if x % d == 0:
            return False
        d += 1
    return True

def big_div(n):
    d = 2
    while d * d <= n:
        if n % d == 0:
            return n // d      # наибольший делитель, не равный n
        d += 1
    return 0                   # n простое: такого делителя нет

n = 350000
found = 0
while found < 6:
    n += 1
    d = big_div(n)
    if d != 0 and not is_prime(d):
        print(n, d)
        found += 1

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

350001 116667
350002 175001
350004 175002
350007 116669
350008 175004
350009 31819

Ответ: 350001 116667 350002 175001 350004 175002 350007 116669 350008 175004 350009 31819