Question

Обозначим через $R$ сумму наименьшего и наибольшего простых делителей натурального числа (исключая 1 и само число). Если простых делителей нет, полагаем $R = 0$. Найдите первые шесть натуральных чисел, больших 6 000 000, для которых $R$ оканчивается на 19.

Accepted Answer

6000002 6000034 6000176 6000190 6000272 6000276

Answer

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

Алгоритм:
1. Функция `is_prime(n)` проверяет, является ли число простым перебором делителей до $\sqrt{n}$.
2. Функция `compute_r(n)` находит все простые делители числа $n$: перебираем потенциальные делители от 2 до $\sqrt{n}$, для каждого делителя $k$ проверяем, простой ли он сам и простой ли $n/k$, добавляем в список.
3. Если список простых делителей пуст, возвращаем 0; иначе возвращаем сумму минимума и максимума.
4. Перебираем числа, начиная с 6 000 001, и выводим первые шесть, для которых $R \bmod 100 = 19$.

```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 compute_r(n):
    prime_divisors = []
    k = 2
    while k * k <= n:
        if n % k == 0:
            if is_prime(k):
                prime_divisors.append(k)
            complement = n // k
            if complement != k and is_prime(complement):
                prime_divisors.append(complement)
        k += 1
    
    if len(prime_divisors) == 0:
        return 0
    return min(prime_divisors) + max(prime_divisors)

count = 0
n = 6000001
while count < 6:
    if compute_r(n) % 100 == 19:
        print(n)
        count += 1
    n += 1
```

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

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