Е25.58 Напишите программу, которая перебирает целые числа, бо́льшие 1 103 285 717

Демонстрационный вариант ЕГЭ 2027 по информатике – задание №25

Вариант 1

Напишите программу, которая перебирает целые числа, большие 1 103 285 717, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых ровно один раз содержит в своей записи 16 (16 — идущие подряд друг за другом в указанном порядке цифры 1 и 6).

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

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

Решение:

Нужно найти первые 5 чисел, больших 1 103 285 717, которые представляются в виде произведения ровно двух простых множителей.
Каждый из этих множителей должен ровно один раз содержать в своей записи последовательность цифр 16.

Используем следующий код:

def is_prime(x):
    if x < 2:
        return False

    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False

    return True


def good(x):
    return is_prime(x) and str(x).count('16') == 1


N = 1_103_285_717
ans = []

for a in range(2, 40000):
    if good(a):
        b = N // a + 1

        k = 0
        while k < 5:
            if b >= a and good(b):
                ans.append((a * b, a))
                k += 1

            b += 1


ans.sort()

for x, a in ans[:5]:
    print(x, a)

def is_prime(x):

if x < 2:

return False

for i in range(2, int(x ** 0.5) + 1):

if x % i == 0:

return False

return True

def good(x):

return is_prime(x) and str(x).count('16') == 1

N = 1_103_285_717

ans = []

for a in range(2, 40000):

if good(a):

b = N // a + 1

k = 0

while k < 5:

if b >= a and good(b):

ans.append((a * b, a))

k += 1

b += 1

ans.sort()

for x, a in ans[:5]:

print(x, a)

Разбор программы

Сначала создаём функцию проверки числа на простоту:

def is_prime(x):
    if x < 2:
        return False

    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False

    return True

def is_prime(x):

if x < 2:

return False

for i in range(2, int(x ** 0.5) + 1):

if x % i == 0:

return False

return True

Если число меньше 2, оно не является простым.
Далее проверяем наличие делителей от 2 до квадратного корня из числа.
Если хотя бы один делитель найден, число составное.

Затем создаём функцию good(), которая проверяет сразу два условия:

def good(x):
    return is_prime(x) and str(x).count('16') == 1

1 2	def good(x): return is_prime(x) and str(x).count('16') == 1

Число должно быть простым и содержать последовательность 16 ровно один раз.

Например, число подходит, если:

1613
3167
65161

1613

3167

65161

при условии, что оно является простым.

Начальная граница:

N = 1_103_285_717

1	N = 1_103_285_717

В список ans будем сохранять найденные произведения и их меньший множитель:

ans = []

ans = []

Далее перебираем возможный первый множитель a:

for a in range(2, 40000):
    if good(a):

1 2	for a in range(2, 40000): if good(a):

Берём только такие значения a, которые являются простыми и содержат 16 ровно один раз.

Для каждого такого a вычисляем минимально возможное значение второго множителя b, при котором произведение будет больше заданного числа:

b = N // a + 1

1	b = N // a + 1

После этого ищем подходящие значения b.

while k < 5:
    if b >= a and good(b):
        ans.append((a * b, a))
        k += 1

    b += 1

while k < 5:

if b >= a and good(b):

ans.append((a * b, a))

k += 1

b += 1

Условие b >= a нужно для того, чтобы a был меньшим из двух множителей.
Именно его требуется вывести во втором столбце ответа.

Если b тоже является простым числом и содержит 16 ровно один раз, сохраняем:

(a * b, a)

1	(a * b, a)

То есть само найденное число и его наименьший простой множитель.

После завершения перебора сортируем все найденные произведения:

ans.sort()

1	ans.sort()

И выводим первые 5:

for x, a in ans[:5]:
    print(x, a)

1 2	for x, a in ans[:5]: print(x, a)

Идея решения

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

Ответ:

1103299319 1693
1103309477 1693
1103322107 16187
1103323021 1693
1103328547 3169

Вариант 2

Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:

– символ «?» означает ровно одну произвольную цифру;

– символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Например, маске 123*4?5 соответствуют числа 123405 и 12300405.

Среди натуральных чисел, не превышающих 10¹⁰, найдите все числа, соответствующие маске 3?12?14*5, делящиеся на 1917 без остатка.

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

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

Решение:

Нужно найти все натуральные числа, не превышающие 10¹⁰, которые одновременно:

соответствуют маске 3?12?14*5;
делятся на 1917 без остатка.

Для проверки соответствия числа маске удобно использовать функцию fnmatch() из модуля fnmatch.

from fnmatch import *

for x in range(1917, 10**10 + 1, 1917):
    if fnmatch(str(x), '3?12?14*5'):
        print(x, x // 1917)

from fnmatch import *

for x in range(1917, 10**10 + 1, 1917):

if fnmatch(str(x), '3?12?14*5'):

print(x, x // 1917)

Разбор программы

Сначала подключаем функцию для работы с масками:

from fnmatch import *

1	from fnmatch import *

В маске:

? обозначает ровно одну произвольную цифру;
* обозначает произвольную последовательность цифр любой длины, в том числе пустую.

Поэтому маска

3?12?14*5

3?12?14*5

описывает числа, которые:
начинаются с цифры 3, затем содержат одну произвольную цифру, после этого 12, ещё одну произвольную цифру, затем 14, далее любое количество цифр и заканчиваются цифрой 5.

Так как искомые числа должны делиться на 1917, нет необходимости перебирать все числа подряд.
Перебираем сразу только кратные 1917:

for x in range(1917, 10**10 + 1, 1917):

1	for x in range(1917, 10**10 + 1, 1917):

Первое значение равно 1917, шаг также равен 1917, поэтому каждое перебираемое число автоматически делится на 1917.

Каждое число переводим в строку и проверяем на соответствие маске:

if fnmatch(str(x), '3?12?14*5'):

1	if fnmatch(str(x), '3?12?14*5'):

Если число подходит, выводим само число и результат его деления на 1917:

print(x, x // 1917)

1	print(x, x // 1917)

Идея решения

Программа перебирает только числа, кратные 1917, что значительно сокращает количество проверок.
Для каждого такого числа с помощью fnmatch() проверяется соответствие маске 3?12?14*5.
Все подходящие числа выводятся вместе с частным от деления на 1917.

Ответ:

351261495 183235
3212614035 1675855
3412614645 1780185
3712414275 1936575
3912414885 2040905