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

КЕГЭ-25. Решаем с помощью решета Эратосфена

Задание 25-01	Задание 25-02	Задание 25-03	Задание 25-04
Задание 25-07	Задание 25-08	Задание 25-09	Задание 25-10
Задание 25-11	Задание 25-12	Задание 25-13	Выводы

Для решения заданий на делители числа бывает полезным использовать решето Эратосфена
В Задачи типа КЕГЭ-25 с решетом Эратосфена приведены приемы и полезные подпрограммы.
Опишем те, которые будут использовать в разборах

sieve(n) - получение множество простых чисел, путем развертки решета Эратосфена
- вход - натуральное число
- выход - список простых чисел, меньших n
fact_(n, P), fact(n, P) - факторизация числа по простым делителям
- вход - натуральное число, множество простых чисел
- выход - список простых делителей числа, включая само число
- fact_ - использует поиск "до корня" (более длинный текст программы)
ksf(n,pd) - вычисление количества делителей и их сумму, на основе результатов программы fact/fact_
- вход - натуральное число, список простых делителей числа (можно получить с помощью fact/fact_)
- выход - колчисество всех делителей числа, сумма всех делителей число
Для получения остальных характеристик (кол-во и сумма нетривиальных делителей, четных/нечетных делителей и т.п. )
специальных программ нет, они используются как самостоятельные в разборе

Задание 25-202601. Сумма крайних делителей: M оканчивается на 6 и кратно 7

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

Напишите программу, которая перебирает целые числа, бо́льшие 950 000, в порядке возрастания
и ищет среди них такие, для которых M оканчивается на цифру 6 и при этом M кратно 7.

В ответе запишите пять строк в порядке возрастания найденных чисел.
В каждой строке сначала найденное число, затем через пробел соответствующее ему значениями M.
Например, для числа 20: M=2+10=12; M оканчивается на 2 и не кратно 7 — число не подходит.

Для решения используем дополнительную программу check, которая возвращает 0 если число не подходит
и значение М - если число удовлетворяет требованиям
(Использование fact_ сокращает время работы с 1,5 сек до 0,07 )

#Задание 25-202601. Сумма крайних делителей: M оканчивается на 6 и кратно 7
def check(n, pd):
  if pd[0] == n : return 0
  m = pd[0] + n//pd[0] # сумма max и min делителей
  if m % 10 == 6 and m % 7 == 0 : return m
  return 0
A, B = 950_000, 1_000_000
P = sieve(B) # получаем все простые до B
k = 5
for n in range(A,B):
  pd = fact_(n, P) # простая факторизация
  if m:= check(n, pd): #используем "моржовый оператор"
    print(n,m)
    k -= 1
    if k == 0 : break

Задание 25-202602. Сумма всех нетривиальных делителей — точный квадрат

Пусть R — сумма всех различных натуральных делителей целого числа, не считая единицы и самого числа.
Если таких делителей нет, R=0.

Напишите программу, которая перебирает целые числа, бо́льшие 600 000, в порядке возрастания
и ищет среди них такие, для которых R является точным квадратом натурального числа (то есть R=k²для некоторого натурального k).

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

Для решения используем дополнительную программу check, которая проверяет сумму число на квадрат (реализовано с запасом на большие числа)
(Использование fact_ сокращает время работы с 2,4 сек до 0,05 )

# Задание 25-202602. Сумма всех нетривиальных делителей — точный квадрат
def check(n) : # проверка числа на полный квадрат, с "защитой от округления"
  if n < 1 : return False
  m = int(n**0.5)
  if n in [(m-1)**2, m**2, (m+1)**2] : return True
  return False
A, B = 600_000, 650_000
P = sieve(B) # получаем все простые до B
k = 5
for n in range(A,B):
  pd = fact_(n, P) # простая факторизация
  kd, sd = ksf(n, pd) # получаем кол-во и сумму всех делителей
  sd = sd - n -1 # преобразуем в сумму собственных делителей 
  if check (sd) :
    print(n,sd) 
    k -= 1
    if k == 0 : break

Задание 25-202603. Разность чётных и нечётных делителей

Пусть D — разность количества чётных и количества нечётных натуральных делителей целого числа,
не считая единицы и самого числа. Если таких делителей нет, D=0.

Напишите программу, которая перебирает целые числа, бо́льшие 1 200 000, в порядке возрастания
и ищет среди них такие, для которых одновременно D>0 и D делится на 5.

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

Для решения используем дополнительную программу check, которая находит разность между количеством четных и нечетных делителей числа
(Использование fact_ сокращает время работы с 1,5 сек до 0,1 )

#Задание 25-202603. Разность чётных и нечётных делителей
def check(n, kd): # проверяет разность между количеством четных и нечетных делителей
  i = 0 # определяем степень вхождения 2 в число
  while n % 2 == 0 : # используем деление, поскольку n только для этого и нужно 
    i += 1
    n = n // 2
  if i == 0 : return 0 # четных делителей нет или число нечетное 
  k1 = kd // (i+ 1) # количество нечетных делителей
  k2 = kd - k1 # количество четных делителей
  d = k2 - k1
  if d > 0 and d % 5 == 0 : return d
  return 0
A, B = 1_200_000, 1_300_000
P = sieve(B) # получаем все простые до B
k = 5
for n in range(A,B,2):
  pd = fact_(n, P) # простая факторизация
  kd, sd = ksf(n, pd) # получаем кол-во и сумму всех делителей
  if D:= check(n,kd): #используем "моржовый оператор"
    print(n, D) 
    k -= 1
    if k == 0 : break

Задание 25-202604. Произведение двух простых, каждый содержит ровно одну цифру 7

Напишите программу, которая перебирает целые числа, бо́льшие 4 500 000, в порядке возрастания
и ищет среди них такие, которые представимы в виде произведения двух простых чисел (не обязательно различных),
в десятичной записи каждого из которых содержится ровно одна цифра 7.

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

Решение возможно как методом перебора, так и методом моделирования
Для решения методом перебора используем дополнительную программу check, которая проверяет, является ли
число произвенедием двух простых, у которых ровно одна цифра 7
(Использование fact_ сокращает время работы с 8,3 сек до 0,4 )

#Задание 25-202604. Произведение двух простых, каждый содержит ровно одну цифру 7
# Метод перебора
def check(n, pd):
  x, y = pd[0], pd[-1]
  if n == x * y and str(x).count('7') == 1 and str(y).count('7') == 1 : return True
  return False
t0 = prt()
A, B = 4_500_000, 5_000_000
P = sieve(B) # получаем все простые до 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

Задание 25-202607. Сумма простых делителей — палиндром

Пусть S — сумма всех различных простых делителей целого числа, не считая самого числа.
Если простых делителей нет (например, число равно 1), S=0.

Напишите программу, которая перебирает целые числа, бо́льшие 4 000 000, в порядке возрастания
и ищет среди них такие, для которых S≠0 и S является палиндромом в десятичной записи
(читается одинаково слева направо и справа налево).

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

Для решения используем дополнительную программу check, которая находит и проверяет сумму собственных простых делителей
(Использование fact_ сокращает время работы с 12,5 сек до 0,3 )

#Задание 25-202607. Сумма простых делителей — палиндром
def check(n, pd): # проверка на палиндром
  s = sum(pd) # сумма простых делителей
  if n == s  : return 0
  ss = str(s)
  if ss == ss[::-1] : return s
  return 0
A, B = 4_000_001, 4_100_000
P = sieve(B) # получаем все простые до B
k = 5
for n in range(A,B):
  pd = fact_(n, P) # простая факторизация
  if s := check(n, pd) : #используем "моржовый оператор"
    print(n, s) 
    k -= 1
    if k == 0 : break

Задание 25-202608. Восьмеричный вес 24 и ровно 4 делителя

Назовём восьмеричным весом натурального числа сумму его цифр в восьмеричной системе счисления.

Напишите программу, которая перебирает целые числа, бо́льшие 750 000, в порядке возрастания и ищет среди них такие, у которых одновременно:

восьмеричный вес равен 24;
число имеет ровно 4 различных натуральных делителя (с учётом 1 и самого числа).

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

Для решения используем дополнительную программу check, которая проверяет число на соответствие правилу 24
(Использование fact_ сокращает время работы с ,15 сек до 0,05 )

#Задание 25-202608. Восьмеричный вес 24 и ровно 4 делителя
def check(n, p=8, s=24): #проверка числа на соответствие
  while n > 0 :
    s -= n % p
    n = n // p
  return s == 0  
A, B = 750_001, 760_000
P = sieve(B) # получаем все простые до B
k = 5
for n in range(A, B):
  if not check(n): continue 
  pd = fact_(n, P) # простая факторизация
  kd, sd = ksf(n, pd) # получаем кол-во и сумму всех делителей
  if kd == 4 :
    print(n, sd) 
    k -= 1
    if k == 0 : break

Задание 25-202609. Произведение трёх простых, оканчивающихся на одну цифру

Рассматриваются целые числа, принадлежащие отрезку [620000;720000], которые представимы в виде
произведения трёх различных простых чисел, оканчивающихся в десятичной записи на одну и ту же цифру.

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

Для решения задачи можно применить метод перебора и метод моделирования

Метод перебора: для решения используем дополнительную программу check, которая проверяет,
что число есть произведение трех соответствующих простых чисел
(без использование fact_ программа требует много времени (более 5 минут), а с fact_ выполняется быстрее 1 сек )
Метод моделирования ответа (это целесообразно, так как необходимо обработать отрезок в 100_000)
То есть перебираем тройки простых чисел, проверяя что они похдят
Пусть x<y<z - такая тройка, тогда
x*x*x, x*y*y <=B
y%10 = x%10 и z%10 = x%10
Вначале отобраем все такие тройки, отсортировать по минимальной разности (возможны и другие решения)

#Задание 25-202609. Произведение трёх простых, оканчивающихся на одну цифру
# вариант 1 Метод перебора
def check(n, pd): # проверка, что делителей 3 и они подходят
  if len(pd) != 3 : return 0
  x, y, z = pd
  if (x % 10 == y % 10 == z % 10) and (x * y * z == n) : return z - x
  return 0
A, B = 620_000, 720_000
P = sieve(B) # получаем все простые до B
k = 0
for n in range(A, B):
  pd = fact(n, P) # простая факторизация
  if D:= check(n, pd) :
      if k == 0 or D < ans[1] : 
        ans = (n, D)
      k += 1
print(k, ans)

#Задание 25-202609. Произведение трёх простых, оканчивающихся на одну цифру
# вариант 2. Моделирование
A, B = 620_000, 720_001
P = sieve(B) # получаем все простые до B
C =[] # список для подходящих чисел 
for i in range(len(P)):
  x = P[i]
  if x**3 > B : continue
  for j in range(i+1, len(P)):
    y = P[j]
    if x % 10 != y % 10 or x*y*y > B : continue
    for ij in range(j + 1,len(P)):
      z = P[ij]
      xyz = x * y * z
      if x % 10 != z % 10 or xyz > B or xyz < A : continue
      C.append((z-x,xyz,x,y,z))
C.sort()
print(len(C), C[0])

Задание 25-202610. Точные четвёртые степени с тремя нетривиальными делителями

Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу.

Найдите все натуральные числа, принадлежащие отрезку [3600000;5800000] и имеющие ровно три нетривиальных делителя.

В ответе через пробел запишите все найденные числа и их наибольшие нетривиальные делители
Формат ввода ответ
число делитель
число делитель

Задача почти устная, поскольку

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

Попробуем решить задание "в лоб" - для нахождение ответа потребовалось менее 25 сек. (используя fact_)

#Задание 25-202610. Точные четвёртые степени с тремя нетривиальными делителями
from time import process_time as prt
t0 = prt()
A, B = 3_600_000, 5_800_000
p0, p1 = A**0.25, B**0.25
print(f'{p0=} {p1=}')
for n in range(int(p0)+1, int(p1)+1):
  print(n**4, n**3)
print(f'time ={prt() - t0}')

#Задание 25-202610. Точные четвёртые степени с тремя нетривиальными делителями
# вариант 2 Метод перебора
def check(n, pd): # проверка, что делителей 3 и они подходят
  if len(pd) != 3 : return 0
  x, y, z = pd
  if (x % 10 == y % 10 == z % 10) and (x * y * z == n) : return z - x
  return 0
A, B = 3_600_000, 5_800_001
P = sieve(B) # получаем все простые до B
for n in range(A, B):
  pd = fact_(n, P) # простая факторизация
  kd, sd = ksf(n, pd) # получаем кол-во и сумму всех делителей
  if kd - 2 == 3 :
    print(n, n//pd[0])

Задание 25-202611. Сумма чётных делителей: M на 0, чётных делителей > 6

Пусть M — сумма всех чётных натуральных делителей целого числа, не считая самого числа. Если чётных делителей нет, M=0.

Напишите программу, которая перебирает целые числа, бо́льшие 2 200 000, в порядке возрастания
и ищет среди них такие, для которых одновременно выполнено:

M оканчивается на цифру 0;
число чётных делителей (не считая самого числа) больше 6.

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

Для решения используем дополнительную программу check, которая находит количество и сумму четных делителей
(Использование fact_ сокращает время работы с ,7 сек до 0,15 )

#Задание 25-202611. Сумма чётных делителей: M на 0, чётных делителей > 6
def check(n, kd, sd): # находит сумму четных делитей и их количество
  i = 0 # определяем степень вхождения 2 в число
  while n % 2 == 0 : # используем деление, поскольку n только для этого и нужно 
    i += 1
    n = n // 2
  k1 = kd // (i+ 1) # количество нечетных делителей
  k2 = kd - k1 # количество четных делителей
  s1 = sd//(2**(i+1) -1)
  s2 = sd - s1
  return k2, s2
A, B = 2_200_002, 2_300_000
P = sieve(B) # получаем все простые до B
k = 5
for n in range(A,B, 2): # интересны только четные числа
  pd = fact_(n, P) # простая факторизация
  kd, sd = ksf(n, pd) # получаем кол-во и сумму всех делителей
  kd2, sd2 = check(n, kd, sd) # получаем кол-во и сумму всех четных делителей
  kd2, sd2 = kd2 -1, sd2 - n # переходим к нетривиальным
  if kd2 > 6 and sd2 % 10 == 0:
    print(n, sd2) 
    k -= 1
    if k == 0 : break

Задание 25-2026012. Числа с ровно 12 делителями в [185 000; 185 100]

Найдите все натуральные числа, принадлежащие отрезку [185000;185100]
и имеющие ровно 12 различных натуральных делителей (с учётом единицы и самого числа).

Для каждого найденного числа определите сумму всех его делителей.

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

Для решения не надо писать дополнительных программ
(Использование fact_ сокращает время работы с ,11 сек до 0,015 )

#Задание 25-2026012. Числа с ровно 12 делителями в [185 000; 185 100]
A, B = 185_000, 185_101
P = sieve(B) # получаем все простые до B
for n in range(A,B):
  pd = fact_(n, P) # простая факторизация
  kd, sd = ksf(n, pd) # получаем кол-во и сумму всех делителей
  if kd == 12 :
    print(n, sd)

Задание 25-202613. M оканчивается на 8, сумма цифр n кратна 7

Пусть M — сумма минимального и максимального натуральных делителей целого числа,
не считая единицы и самого числа. Если таких делителей нет, M=0.

Напишите программу, которая перебирает целые числа, бо́льшие 1 200 000, в порядке возрастания
и ищет среди них такие, для которых одновременно выполнено:

значение M оканчивается на цифру 8;
сумма цифр самого числа в десятичной записи кратна 7.

В ответе запишите первые пять найденных чисел в порядке возрастания, через пробел от каждого числа его значение M.
Каждая пара (число M) записывается в отдельной строке.

Для решения используем дополнительную программу check, которая находит и проверяет сумму цифр числа
(Использование fact_ сокращает время работы с 1,8 сек до 0,8 )

#Задание 25-202613. M оканчивается на 8, сумма цифр n кратна 7
def check(n): # проверка суммы цифр числа на кратность 7
  return sum(int(a) for a in str(n)) % 7 == 0
A, B = 1_200_001, 1_300_000
P = sieve(B) # получаем все простые до B
k = 5
for n in range(A,B):
  if not check(n) : continue # проверка числа
  pd = fact(n, P) # простая факторизация
  if n == pd[0] : continue
  M = pd[0] + n // pd[0]
  if M % 10 == 8 :
    print(n, M)
    k -= 1
    if k == 0 : break

Некоторый выводы
Использование метода решета Эратосфена и пары базовых программ позволят
достаточно просто решать большинство задач как "методом перебора" так и "методом моделирования"
Использование "быстрой" простой факторизации может не потребоваться.
"Метод моделирования" может быть единственно оправданным способом решения, если нужно найти все числа на "большом отрезке"
или в некоторых "хитрых" заданиях (таких на КЕГЭ не бывает)

Печать