ЕГЭ 25

Задание 25 ЕГЭ по информатике: 25. Теория чисел в программировании — вариант Пересдача 08.07.26

Вариант Пересдача 08.07.26

Варианты

Задание 25 ЕГЭ по информатике: 25. Теория чисел в программировании — вариант Пересдача 08.07.26

Пересдача 08.07.26

Секундомер

0 XP

0 / 0

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

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

Количество строк в таблице для ответа избыточно.

Решение

Список простых

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True


primes = [x for x in range(2, 100000)
          if str(x).count("67") == 1 and is_prime(x)]


ans = []

for p in primes:
    q = max(p, 2_726_695_891 // p + 1)
    found = 0
    while found < 3:
        if str(q).count("67") == 1 and is_prime(q):
            ans.append((p * q, p))
            found += 1
        q += 1

ans.sort()
print(*ans[:5], sep='\n')

Сначала собираем простые числа с «67» — это кандидаты на меньший множитель. Для каждого ищем второй множитель (тоже простой с «67»), чтобы произведение было больше порога. Потом берём пять самых маленьких произведений.

Переменная	Значение
нет переменных