Дошкольникам
1 класс
2 класс
3 класс
4 класс
5 класс
6 класс
7 класс
8 класс
9 класс
10 класс
11 класс
ОГЭ
ЕГЭ
ВУЗ
Для всех
Назад

25. Обработка целочисленной информации: Напишите программу, которая перебирает целые числа, большие…

Задание #295974
Решено верно
Решено неверно
Сообщить о проблеме

Пусть $M$ – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение $M$ считается равным нулю. Напишите программу, которая перебирает целые числа, большие $8,007,524,668$, в порядке возрастания и ищет среди них такие, для которых $M$ больше $110,000$, является простым числом и в своём написании содержит последовательность цифр $991$ ровно один раз.

В ответе запишите в первом столбце таблицы первые $5$ найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения $M$.

Например, для числа $49$ $M=14$; для числа $42$ $M=9$.








Так как $M$ должно быть простым числом больше $110,000$, оно нечётное. Если исходное число нечётное, его минимальный и максимальный простые делители также нечётные, поэтому их сумма будет чётной. Значит, подходящее число обязательно чётное.

Следовательно, минимальный простой делитель равен $2$, и $M=2+\text{максимальный простой делитель}$.

Будем перебирать только чётные числа и находить их максимальный простой делитель.

def prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2

    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2

    return True


def max_div(n):
    m = 0

    while n % 2 == 0:
        m = 2
        n //= 2

    d = 3
    while d * d <= n:
        while n % d == 0:
            m = d
            n //= d
        d += 2

    if n > 1:
        m = max(m, n)

    return m


n = 8007524670
k = 0

while k < 5:
    d = max_div(n)
    M = 2 + d

    if M > 110000 and prime(M) and str(M).count('991') == 1:
        print(n, M)
        k += 1

    n += 2

Функция max_div(n) находит максимальный простой делитель числа $n$.

Условие str(M).count(‘991’) == 1 проверяет, что последовательность цифр $991$ встречается в записи числа $M$ ровно один раз.

Программа выведет:

Число$M$
$8007539144$$149911$
$8007540788$$153991171$
$8007540856$$142991803$
$8007547448$$9910333$
$8007550626$$150991$
Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

Предложить улучшение