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

Задание 25_Знакомство

Формулировка задачи (КЕГЭ 2026_ДВ /95463

Пусть M – сумма минимального и максимального простых натуральных делителей целого числа, не считая самого числа. Если таких делителей у числа нет, то значение M считается равным нулю.

Напишите программу, которая перебирает целые числа, большие 5 800 000, в порядке воз- растания и ищет среди них такие, для которых М больше 80 000 и является палиндромом, т.е. одинаково читается слева направо и справа налево.

В ответе запишите в первом столбце таблицы первые пять найденных чисел в порядке возрастания, а во втором столбце – соответствующие им значения М. Например, для числа 298 M = 2 + 149 = 151.

Задание такого типа можно решать с помощью программы факторизации числа на простые числа
Для этого будем использовать процедуру поиска минимального делителя числа

def mdel(n):
  if n % 2 == 0 : return 2
  if n < 9 : return n
  for d in range(3, int(n**0.5) + 3, 2):
    if n % d == 0 : return d
  return n
def pfact(n) :
  pd = []
  while n > 1 :
    m = mdel(n) 
    pd.append(m)
    while n % m == 0 :
      n = n // m
  return pd
def palindrom(n):
  s = int(str(n)[::-1])
  return s == n
N = 5_800_000
k = 5
while k > 0 :
  N +=1
  pd = pfact(N)
  if pd[-1] == N : continue
  M = pd[0] +pd[-1]
  if M > 80_000 and palindrom(M) :
    print(N, M)
    k -= 1

Формулировка задачи (КЕГЭ 25, (2026 Резерв ID 95900)

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

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

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

Для решения задания отберем все простые числа, которые меньше 1_000_000 и содержат одну комбинацию числа 16
Сделаем это через "решето Эратосфена". Далее посмотрим, что делать.

from time import process_time as prt
def check(m) :
  if str(m).count('16') == 1 : return True
  return False
def sieve(N) :
  R = [0,0,1,1] +[0,1]*(N//2)
  for d in range(3, int(N**0.5 + 1)) :
    R[d*d:N:2*d] = [0]*(len(range(d*d,N,2*d)))
  P = [i for i in range(N) if (R[i] == 1) and check(i) ]
  return P
t0 = prt()
N, M = 1_104_285_717, 1_200_000_000
pm = 163
Pr = sieve(M//163 + 1)
print(f'для развертки "решета" потребовалось {prt() - t0}')
P = [x for x in Pr if x * x < M]
Q = [x for x in Pr if x * x > N]
df = []
for x in P :
  k = 5
  for y in Q :
    r = x * y
    if r > N :
      df.append((r, x, y))
      k -= 1
      if k == 0 : break
df.sort()
for i in range(5) :
  print(df[i][0], df[i][1], df[i][2])
print(f'для решения задания потребовалось {prt() - t0}', len(df))

Для решения "в лоб" нужно было перебрать около 72000 чисел (используя правило окончаний произведения простых больших 10, можно сократить до 30 тысяч)
Если для каждого находить минимальный делитель и проверять его в списке простых чисел с одной комбинацией 16 и не превосходящих 36000 (36000**2 > разумного 1_200_000_000)
или проверять на делимость на одно из 175 чисел (столько "маленьких" простых), а затем остаток, то решение будет сложнее и более трудоемким.

Приведем "более понятное" решение

После получения списка простых, двойным перебором определим "интересные числа" в выбранном интервале
возьмем от 1_100_000_000 до 1_200_000_000

from time import process_time as prt
def check(m) :
  if str(m).count('16') == 1 : return True
  return False
def sieve(N) :
  R = [0,0,1,1] +[0,1]*(N//2)
  for d in range(3, int(N**0.5 + 1)) :
    R[d*d:N:2*d] = [0]*(len(range(d*d,N,2*d)))
  P = [i for i in range(N) if (R[i] == 1) and check(i) ]
  return P
t0 = prt()
N, M = 1_104_285_717, 1_200_000_000

pm = 163
P = sieve(M//163 + 1)
print(f'для развертки "решета" потребовалось {prt() - t0}')
df = []
for i in range(len(P)) :
  x = P[i]
  for j in range(i, len(P)) :
    y = P[j]
    r =  x * y
    if r < N : continue
    if r > M : break
    df.append((r,x,y))  
df.sort()
for i in range(5) :
  print(df[i][0], df[i][1], df[i][2])
print(f'для решения задания потребовалось {prt() - t0}', len(df))

Печать