Question

Пусть $M$ — сумма максимального и минимального простых делителей целого числа. Если у числа нет простых делителей, то $M = 0$. Напишите программу, которая перебирает целые числа, начиная с 7 500 001, в порядке возрастания и ищет первые пять таких чисел, для которых $M$ заканчивается на 32 и кратно общему количеству простых делителей.

Accepted Answer

7500045
7500107
7500131
7500317
7500589

Answer

Идея решения: для каждого числа найти все его простые делители, вычислить сумму минимального и максимального, проверить условия на окончание и делимость.

Алгоритм:

1. Функция `is_prime(n)` проверяет, является ли число простым перебором делителей до $\sqrt{n}$.

2. Функция `prime_divisors(n)` находит все простые делители числа $n$:
   - перебираем потенциальные делители $k$ от 2 до $\sqrt{n}$;
   - если $k$ делит $n$, добавляем $k$ и $n/k$ в множество (если они простые);
   - возвращаем отсортированный список простых делителей.

3. Основной цикл:
   - начинаем с числа 7 500 001;
   - для каждого числа получаем список простых делителей;
   - если список не пуст, вычисляем $M$ как сумму первого и последнего элемента;
   - проверяем условия: $M \bmod 100 = 32$ и $M \bmod (	ext{количество делителей}) = 0$;
   - выводим число и увеличиваем счётчик;
   - останавливаемся после пяти найденных чисел.

```python
def is_prime(n):
    if n < 2:
        return False
    k = 2
    while k * k <= n:
        if n % k == 0:
            return False
        k += 1
    return True

def prime_divisors(n):
    divisors = set()
    k = 2
    while k * k <= n:
        if n % k == 0:
            divisors.add(k)
            divisors.add(n // k)
        k += 1
    return sorted([x for x in divisors if is_prime(x)])

n = 7500001
count = 0
while count < 5:
    p = prime_divisors(n)
    if p:
        M = p[0] + p[-1]
        if M % 100 == 32 and M % len(p) == 0:
            print(n)
            count += 1
    n += 1
```

Сложность: $O(k \cdot \sqrt{n})$, где $k$ — количество найденных чисел (5), $n$ — значение числа. Для каждого числа факторизация выполняется за $O(\sqrt{n})$.

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