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

Решение.
Требуются первые пять чисел, строго больших 5700000. Начинаем с 5700001 и рассматриваем целые n подряд в порядке возрастания.
Разложим n на простые множители. Каждый простой делитель записываем один раз, независимо от степени. Само n исключаем: если n простое, допустимых простых делителей нет и M = 0.
Пусть p — наименьший, q — наибольший из оставшихся простых делителей. Тогда M = p + q. Если простой делитель только один, минимум и максимум совпадают, поэтому M равняется удвоенному делителю; такой случай нельзя отбрасывать.
При разложении последовательно делим остаток на каждый найденный простой множитель до исчезновения его степени. Если после проверки всех p с p² ≤ остатку остаётся число больше 1, оно простое: составное число обязательно имело бы делитель не больше своего квадратного корня.
Проверяем строгое ограничение M больше 70000. Для целого r = ⌊√M⌋ число M является полным квадратом тогда и только тогда, когда r² = M.
n = 5702279 = 11 · 518389.
Различные простые делители: 11, 518389.
M = 11 + 518389 = 518400.
518400 больше 70000; 720² = 518400.
n = 5702517 = 3² · 633613.
Различные простые делители: 3, 633613.
M = 3 + 633613 = 633616.
633616 больше 70000; 796² = 633616.
n = 5702960 = 2⁴ · 5 · 71287.
Различные простые делители: 2, 5, 71287.
M = 2 + 71287 = 71289.
71289 больше 70000; 267² = 71289.
n = 5702985 = 3² · 5 · 126733.
Различные простые делители: 3, 5, 126733.
M = 3 + 126733 = 126736.
126736 больше 70000; 356² = 126736.
n = 5703095 = 5 · 1140619.
Различные простые делители: 5, 1140619.
M = 5 + 1140619 = 1140624.
1140624 больше 70000; 1068² = 1140624.
В программе решето строит простые числа до 100000. Перебор ограничен сверху 10¹⁰, чей квадратный корень равен 100000, поэтому списка достаточно для полного разложения каждого проверяемого n и проверки простоты M. Ниже показано, что все пять результатов найдены раньше этой границы; после пятого программа сразу завершается.
Полный последовательный перебор от 5700001 до 5703095 включительно проверяет 3095 чисел. Условие выполняется ровно для пяти перечисленных 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(5700001, 10 ** 10 + 1):
    d = prime_divisors(n)
    M = d[0] + d[-1] if d else 0
    if gt(M, 70000) and isqrt(M) ** 2 == M:
        print(n, M)
        found += 1
        if found == 5:
            break
assert found == 5

Результат: в каждой строке слева n, справа M.
5702279 — 518400
5702517 — 633616
5702960 — 71289
5702985 — 126736
5703095 — 1140624
Ответ: (5702279; 518400), (5702517; 633616), (5702960; 71289), (5702985; 126736), (5703095; 1140624).