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

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

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

Напишите программу, которая перебирает целые числа, большие $2,018,974,447$, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых ровно один раз содержит в своей записи $43$ ($43$ – идущие подряд друг за другом в указанном порядке цифры $4$ и $3$).

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








Если число имеет вид $n=p\cdot q$, где $p$ и $q$ — простые числа, то достаточно найти наименьший делитель $p$. После этого проверяем, что второй множитель $q=\dfrac{n}{p}$ тоже является простым числом и каждый из множителей содержит 43 ровно один раз.

from math import isqrt

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

    for d in range(3, isqrt(n) + 1, 2):
        if n % d == 0:
            return False

    return True


def f(n):
    if n % 2 == 0:
        p = 2
    else:
        p = 0

        for d in range(3, isqrt(n) + 1, 2):
            if n % d == 0:
                p = d
                break

        if p == 0:
            return 0

    q = n // p

    if (str(p).count('43') == 1 and
        str(q).count('43') == 1 and
        prime(q)):
        return p

    return 0


n = 2018974448
k = 0

while k < 5:
    d = f(n)

    if d != 0:
        print(n, d)
        k += 1

    n += 1

Функция f(n) находит наименьший простой множитель числа $n$. Затем проверяется, что второй множитель тоже простой и последовательность 43 встречается в каждом множителе ровно один раз.

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

ЧислоНаименьший множитель
$2018977769$$27143$
$2018980091$$9437$
$2018983349$$643$
$2018997619$$43$
$2019003907$$4643$
Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

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