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

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

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

Пусть $M$ – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение $M$ считается равным нулю. Напишите программу, которая перебирает целые числа, большие $8,007,494,154$, в порядке возрастания и ищет среди них такие, для которых $M$ больше $80,000$, является простым числом и в своём написании содержит последовательность цифр $567$ ($567$ – идущие подряд друг за другом в указанном порядке цифры $5$, $6$ и $7$) ровно один раз.

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

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








Если исходное число нечётное, то его минимальный и максимальный простые делители нечётные. Их сумма $M$ будет чётной. Так как $M>80,000$ и должно быть простым, такие числа нам не подходят.

Значит, перебираем только чётные числа. Для них минимальный простой делитель равен $2$, поэтому $M=2+\text{максимальный простой делитель}$.

from math import isqrt

def prime(n):
    if n < 2:
        return False
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            return False
    return True


def max_div(n):
    m = 2

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

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

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

    return m


n = 8007494156
k = 0

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

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

    n += 2

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

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

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

Число$M$
$8007495062$$615679$
$8007495772$$5671033$
$8007531302$$856789$
$8007532410$$5679103$
$8007559070$$1567039$
Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

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