Question

Пусть $M$ — сумма минимального и максимального натуральных делителей целого числа, не считая единицы и самого числа. Если таких делителей у числа нет, то значение $M$ считается равным нулю.

Напишите программу, которая перебирает целые числа, большие 700 000, в порядке возрастания и ищет среди них такие, для которых значение $M$ оканчивается на 4. Выведите первые пять найденных чисел и соответствующие им значения $M$.

Формат вывода: для каждого из пяти таких найденных чисел в отдельной строке сначала выводится само число, затем — значение $M$.

Accepted Answer

700004 350004
700009 41194
700023 233344
700024 350014
700044 350024

Answer

Идея решения: для каждого числа найти все его делители (кроме 1 и самого числа), вычислить сумму минимального и максимального из них, и проверить, оканчивается ли эта сумма на 4.

Алгоритм:
1. Для каждого числа $n$ найдём все делители, перебирая числа от 2 до $\sqrt{n}$.
2. Если делитель $i$ найден, добавим в список и $i$, и $n/i$ (они оба являются делителями).
3. Если список делителей не пуст, вычислим $M$ как сумму минимального и максимального делителя.
4. Проверим, оканчивается ли $M$ на 4 (остаток от деления на 10 равен 4).
5. Выведем первые пять чисел, удовлетворяющих условию.

```python
def divisors(n):
    d = set()
    k = 2
    while k * k <= n:
        if n % k == 0:
            d.add(k)
            d.add(n // k)
        k += 1
    return sorted(d)

n = 700000
count = 0
while count < 5:
    n += 1
    d = divisors(n)
    if d:
        m = min(d) + max(d)
        if m % 10 == 4:
            print(n, m)
            count += 1
```

Программа начинает перебор с 700 001 и для каждого числа вычисляет множество делителей (исключая 1 и само число). Если делители существуют, находит их сумму минимального и максимального. Когда сумма оканчивается на 4, число и значение $M$ выводятся. Процесс продолжается до нахождения пяти таких чисел.

Задание №25ПрограммированиеЕГЭ по информатике