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

Задачи типа КЕГЭ-25 с решетом Эратосфена

Для решения заданий типа КЕГЭ-25 можно вначале построить необходимое множество простых чисел, а затем использовать его

Построение множества простых чисел лучше всего реализовать построением решета Эратосфена
Для решения заданий для чисел нужно находить различные характеристики:
- количество делителей
- сумму делителей
- минимальный и максимальный делитель
- простые делители числа
- и т.п.

Приведем основные подпрограммы (без излишней оптимизации), а затем рассмотрим подход на примере решения задания одного из вариантов апрельской ЕГКР (2026 года)

def sieve(n) :
  # получение множества всех простых чисел, меньших  n
  M = [0, 0, 1] + [1, 0] * (n // 2) #сразу исключаем четные числа
  for d in range(3, int(n**0.5) + 1, 2):
    if M[d] : # проверка d на простоту
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2)) # так проще и быстрее
  return [i for i in range(n) if M[i]]  # возвращаем множество простых  
def fact (n, P) : # получение простых множителей числа (базовый вариант)
  return [i for i in P if n % i == 0] # результат простой факторизации
def fact_ (n, P) : # получение простых множителей числа (быстрый вариант)
  pd = []
  for i in P :
    if i * i > n : break
    if n % i == 0 : 
      pd.append (i)
      while n % i == 0 : n = n//i
  pd.append(n)
  return pd 
def ksf(n, pd) : # получение количества и суммы делителей по простой факторизации
  k, s = 1, 1 # для подсчета используются формулы нахождения через факторизацию
  for d in pd :
    i = 1
    while n % d == 0 :
      i += 1
      n = n // d
    k *= i
    s *= ((d**i - 1)//(d-1))
  return k, s
try :
  n = int(input())
except : 
  n = 1580
P = sieve(n+1)
pd = fact_(n, P)
kd,sd = ksf(n, pd)
print(f'количество простых чисел не превосходящих {n} равно {len(P)} {P[:5]}...{P[-5:]}')
print(f'простые делители числа {n} есть {pd}')
print(f'количество всех делителей числа {n} равно {kd}')
print(f'сумма всех делителей числа {n} равна {sd}')
# нахождение характеристик четных и нечетных делителей
i, j = 0, 1 # определяем степень вхождения 2 в число
while n % (2*j) == 0 :
  i, j = i + 1, 2 * j
k1 = kd // (i+ 1) # количество нечетных делителей
k2 = kd - k1 # количество четных делителей
s1 = sd //(2 * j - 1) # сумма нечетных делителей
s2 = sd - s1 # сумма четных делителей
print(f'количество нечетных делителей числа {n} равно {k1}, а четных {k2}')
print(f'сумма нечетных делителей числа {n} равна {s1}, а четных {s2}')

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

Задание можно решить двумя "подходами"

Перебор чисел больших заданного и проверка на удовлетворение условиям
Моделирование: отбираем подходящие простые, формируем список попарных произведений и берем минимальные

Реализуем оба подхода. Предположим, что искомые числа не будут превышать 9_000_000 (это очень грубая оценка, если не будет достаточной, то увеличим). Итак

определим отрезок [A,B]
развернем решето до B (чтобы можно было и простые отлавливать)
далее в зависимости от подхода

Для эффективного использования лучше применять подпрограмму fact_ (это просмотр простых делителей "до корня")
На данной задаче выигрыш более чем в 50 раз ( здесь решение с fact_ занимает менее 5 сек, а использование fact результата не дает и при лимите в 100 сек)

# Подход 1. Перебор
from time import process_time as prt
def sieve(n) :
  M = [0, 0, 1] + [1, 0] * (n // 2) 
  for d in range(3, int(n**0.5) + 1, 2):
    if M[d] : 
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2)) 
  return [i for i in range(n) if M[i]]    
def fact_ (n, P) : # получение простых множителей числа (быстрый вариант)
  pd = []
  for i in P :
    if i * i > n : break
    if n % i == 0 : 
      pd.append (i)
      while n % i == 0 : n = n//i
  pd.append(n)
  return pd 
def fact (n, P) : # получение простых множителей числа (базовый вариант)
  if n in P : return [n]
  return [i for i in P if n % i == 0] # результат простой факторизации
def check(n, pd):
  if len(pd) > 2 : return False
  x, y = pd[0], pd[-1]
  if (n == x * y) and (str(x).count('1') == 2) and (str(y).count('1') == 2) : return True
  return False
t0 = prt()
A, B = 8_568_642, 9_000_000
P = sieve(B)
k = 5
for n in range(A,B) :
  pd = fact_(n, P)
  if check(n, pd) :
    print(n, pd[-1])
    k -= 1
    if k == 0 : 
      break
print(f'time={prt() - t0}')

При решении методом моделирования можно использовать генераторы (это упрощает код)
Видим, что метод моделирования для данной задачи более эффективен

# Подход 2. Моделирование
from time import process_time as prt
def sieve(n) :
  M = [0, 0, 1] + [1, 0] * (n // 2) 
  for d in range(3, int(n**0.5) + 1, 2):
    if M[d] : 
      dd, d2 = d * d, 2 * d
      M[dd:n:d2] = [0]*len(range(dd, n, d2)) 
  return [i for i in range(n) if M[i]]    
def check(n, pd):
  if len(pd) > 2 : return False
  x, y = pd[0], pd[-1]
  if (n == x * y) and (str(x).count('1') == 2) and (str(y).count('1') == 2) : return True
  return False
t0 = prt()
A, B = 8_568_642, 9_000_000
P = sieve(B)
P = [i for i in P if str(i).count('1') == 2]
C = []
for i in range(len(P)) :
  x = P[i]
  if x * x > B : continue 
  C += [(x * P[j], P[j]) for j in range(i, len(P)) if A<= x * P[j] < B] 
C.sort()
for xy in C[:5] :
  print(*xy)
print(f'time={prt() - t0}')

Ниже приведен список задач, на которых можно проверить данный подход

Задание 25-202601. Сумма крайних делителей: M оканчивается на 6 и кратно 7
Задание 25-202602. Сумма всех нетривиальных делителей — точный квадрат
Задание 25-202603. Разность чётных и нечётных делителей
Задание 25-202604. Произведение двух простых, каждый содержит ровно одну цифру 7
Задание 25-202607. Сумма простых делителей — палиндром
Задание 25-202608. Восьмеричный вес 24 и ровно 4 делителя
Задание 25-202609. Произведение трёх простых, оканчивающихся на одну цифру
Задание 25-202610. Точные четвёртые степени с тремя нетривиальными делителями
Задание 25-202611. Сумма чётных делителей: M на 0, чётных делителей > 6
Задание 25-2026012. Числа с ровно 12 делителями в [185 000; 185 100]
Задание 25-202613. M оканчивается на 8, сумма цифр n кратна 7

Разбор заданий можно посмотреть в КЕГЭ-25. Решаем с помощью решета Эратосфена

Печать