Задание EGEINF490128: Делители, маски и отбор чисел

Решение.
Требуются первые пять чисел, строго больших 7800000. Начинаем с 7800001 и рассматриваем целые n подряд в порядке возрастания.
Разложим n на простые множители. Каждый простой делитель записываем один раз, независимо от степени. Само n исключаем: если n простое, допустимых простых делителей нет и M = 0.
Пусть p — наименьший, q — наибольший из оставшихся простых делителей. Тогда M = p + q. Если простой делитель только один, минимум и максимум совпадают, поэтому M равняется удвоенному делителю; такой случай нельзя отбрасывать.
При разложении последовательно делим остаток на каждый найденный простой множитель до исчезновения его степени. Если после проверки всех p с p² ≤ остатку остаётся число больше 1, оно простое: составное число обязательно имело бы делитель не больше своего квадратного корня.
Окончание 63 означает остаток 63 при делении M на 100. Пусть k — количество различных простых делителей n; дополнительно нужен нулевой остаток при делении M на k. Для простого n значение M = 0 не проходит проверку окончания.
n = 7800610 = 2 · 5 · 780061.
Различные простые делители: 2, 5, 780061.
M = 2 + 780061 = 780063.
780063 = 100 · 7800 + 63; k = 3; 780063 = 3 · 260021.
n = 7801042 = 2 · 461 · 8461.
Различные простые делители: 2, 461, 8461.
M = 2 + 8461 = 8463.
8463 = 100 · 84 + 63; k = 3; 8463 = 3 · 2821.
n = 7801312 = 2⁵ · 131 · 1861.
Различные простые делители: 2, 131, 1861.
M = 2 + 1861 = 1863.
1863 = 100 · 18 + 63; k = 3; 1863 = 3 · 621.
n = 7801916 = 2² · 239 · 8161.
Различные простые делители: 2, 239, 8161.
M = 2 + 8161 = 8163.
8163 = 100 · 81 + 63; k = 3; 8163 = 3 · 2721.
n = 7802032 = 2⁴ · 7 · 69661.
Различные простые делители: 2, 7, 69661.
M = 2 + 69661 = 69663.
69663 = 100 · 696 + 63; k = 3; 69663 = 3 · 23221.
В программе решето строит простые числа до 100000. Перебор ограничен сверху 10¹⁰, чей квадратный корень равен 100000, поэтому списка достаточно для полного разложения каждого проверяемого n и проверки простоты M. Ниже показано, что все пять результатов найдены раньше этой границы; после пятого программа сразу завершается.
Полный последовательный перебор от 7800001 до 7802032 включительно проверяет 2032 чисел. Условие выполняется ровно для пяти перечисленных n. Все меньшие допустимые кандидаты проверены, поэтому это именно первые пять чисел.
Проверка результата.
Воспроизводимая программа Python:

from math import isqrt
from operator import gt, lt

limit = 100000
flags = [True] * (limit + 1)
flags[0] = flags[1] = False
for p in range(2, isqrt(limit) + 1):
    if flags[p]:
        for multiple in range(p * p, limit + 1, p):
            flags[multiple] = False
primes = [p for p in range(2, limit + 1) if flags[p]]

def prime_divisors(n):
    rest = n
    result = []
    for p in primes:
        if gt(p * p, rest):
            break
        if rest % p == 0:
            result.append(p)
            while rest % p == 0:
                rest = divmod(rest, p)[0]
    if rest != 1:
        result.append(rest)
    return [] if result == [n] else result

def is_prime(n):
    if lt(n, 2):
        return False
    for p in primes:
        if gt(p * p, n):
            return True
        if n % p == 0:
            return False
    return True

found = 0
for n in range(7800001, 10 ** 10 + 1):
    d = prime_divisors(n)
    M = d[0] + d[-1] if d else 0
    if M % 100 == 63 and M % len(d) == 0:
        print(n, M)
        found += 1
        if found == 5:
            break
assert found == 5

Результат: в каждой строке слева n, справа M.
7800610 — 780063
7801042 — 8463
7801312 — 1863
7801916 — 8163
7802032 — 69663
Ответ: (7800610; 780063), (7801042; 8463), (7801312; 1863), (7801916; 8163), (7802032; 69663).