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

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

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

Напишите программу, которая перебирает целые числа, большие $2,626,695,891$, в порядке возрастания и ищет среди них числа, представимые в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых ровно один раз содержит в своей записи $67$ ($67$ – идущие подряд друг за другом в указанном порядке цифры $6$ и $7$).

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








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

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 f(n):
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            q = n // d

            if (prime(q) and
                str(d).count('67') == 1 and
                str(q).count('67') == 1):
                return d

            return 0

    return 0


n = 2626695892
k = 0

while k < 5:
    d = f(n)

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

    n += 1

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

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

ЧислоНаименьший множитель
$2626696861$$6793$
$2626700987$$1567$
$2626704089$$167$
$2626711691$$2267$
$2626713493$$67$
Показать
Очки опыта 20
Спросить Зави
0 заданий сегодня

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