Статья Автор: Лебедев Дмитрий Алексеевич

Метод моделирования в задаче 25

Рассмотрим задание 25 из ЕГКР апреля 2025 года

Напишите программу, которая перебирает целые числа, большие 8 996 452, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно две цифры 3.

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

Что можно понять из условия:

Нужные числа могут встречаться редко - поскольку они не просто произведение двух простых, а особых простых
Вроде надо найти не все числа, а только 5, значит числа не так далеко от заданной границы (можно предположить, что они врядли больше 10_000_000)
Простые кандидаты не меньше 200 ( 133 - делится на 7), это значит, что максимальное точно не более 50_000

Из этих предположений получаем идею решения:

Отобрать все простые числа до 50000 у которых ровно две цифры 3
Перебрать все пары, произведение которых более заданной границы
Отсортировать и вывести ответ

можно немного упростить, но делать этого не будем, чтобы понять какие цифры получаются
Самое сложное реализовать 1 этап. Есть два способа:

A. Решето Эратосфена
B. Перебор всех чисел, проверка на число 3 и простоту

Вначале реализуем способ B (как более "понятный")

def mindel(n): # поиск минимального делителя числа
  if n % 2 == 0 : return 2 # для четных это 2
  if n < 9 : return n # проверяем 3, 5, 7 (и 1)
  for d in range(3, int(n**0.5) + 2, 2): # теперь до корня от 3 с шагом 2 (нечётные)
    if n % d == 0 : return d # число составное и минимальный найден
  return n # число простое
def check (n) :
  if str(n).count('3') != 2 : return False # проверка на число 3
  if n != mindel(n) : return False # проверка на простоту
  return True
N = 8_996_452 # параметр задачи
P = [x for x in range(3,50000,2) if check(x)] #отбор простых
print(f'{len(P)=} {P[:5]=} {P[-5:]=}')
Ans = sorted(set([(x*y, max(x, y), min(x,y)) for x in P for y in P if x*y > N]))
print(f'{len(Ans)=}', *Ans[:5], sep='\n')

На решение задания потребовалось менее 1 секунды при коде без всякой оптиминизации
Приведем решение с Решетом Эратосфена

def sieve (M):
  R = [0,0,1,1] + [0,1]*(M//2) #массив решета с вычеркнутыми чЁтными (кроме 2) и 1
  for d in range(3, int(M**0.5) + 1, 2): # числа для вычеркивания - нечётные и до корня
    if R[d] == 0 : continue # а также простые
    R[d*d:M:2*d] = [0] *len(range(d*d,M,2*d)) # слева срез для обнуления - справа список из нулей той же длины
  return [p for p in range(2, M) if R[p] and str(p).count('2') == 2] # добавили условие отбора нужных
N = 8_120_140 # параметр задачи
P = sieve(50000) #отбор простых
print(f'{len(P)=} {P[:5]=} {P[-5:]=}')
Ans = sorted(set([(x*y, max(x, y), min(x,y)) for x in P for y in P if x*y > N ]))
print(f'{len(Ans)=}', *Ans[:5], sep='\n')

Время одинаковое, поскольку основное время тратиться на построение массима Ans
Предлагаем самостоятельно решить это задание стандартным методом - перебором чисел, проверкой на число делителей и их состав
Почему такой подход полез/необходим - давайте представим, что надо
Найти все такие числа на отрезке от 9_000_000 до 10_000_000 и в качестве ответа вывести:

количество и сумму таких чисел

Решение этой задачи будет более быстрым (не нужна сортировка)

Печать