Question

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

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

Accepted Answer

7000018
7000076
7000088
7000096
7000124

Answer

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

Для поиска простых делителей числа $n$ переберём все делители от 2 до $\sqrt{n}$. Если $i$ делит $n$, то оба $i$ и $n/i$ — потенциальные делители; проверим каждый на простоту. Простоту числа проверим пробным делением до его квадратного корня.

Основной цикл начинается с 7 000 001 и продолжается до тех пор, пока не найдены пять подходящих чисел.

```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 sum_min_max_prime_divisors(n):
    divisors = set()
    k = 2
    while k * k <= n:
        if n % k == 0:
            divisors.add(k)
            divisors.add(n // k)
        k += 1
    
    prime_divisors = [x for x in divisors if is_prime(x)]
    
    if prime_divisors:
        return min(prime_divisors) + max(prime_divisors)
    else:
        return 0

count = 0
n = 7000000
while count < 5:
    n += 1
    M = sum_min_max_prime_divisors(n)
    if M % 100 == 13:
        print(n)
        count += 1
```

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

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