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

Проблема М. Найди числа на отрезке по свойству

Проблема M. Найди числа на отрезке по их свойствам.

Мотив простых чисел и отрезки достаточно частые гости КЕГЭ (задание повышенного уровня)
Попробуем составить "пример" такого задания:

Дан отрезок [A;B] (А, В большие числа, например в районе 10¹² )
Надо среди всех чисел отрезка найти все (или заданное число) числа, удовлетворяющие условию:
- число удовлетворяет маске (например *7*7*7*)
- число имеет одни собственных делитель, который удовлетворяет маске (например *1*5*8*)

Путь решения может использовать следующие умозаключения:

Если число имеет один собственный делитель, то оно есть квадрат простого числа из отрезка
[A**0.5; B**0.5]
Числа для пункта 1) можно получить с использованием "решета Эратосфена"
Просеем по маскам простое число и его квадрат

Задача 1 Числа с одним собственным делителем и совпадающие с ним по составу

Напишите программу, которая на отрезке [A; B] находит все "особые" числа отрезка.
Число N называется особым, если выполнены следующие условия:

число N имеет один собственный делитель P
(собственный делитель, это делитель отличный от 1 и самого числа)
составы десятичных записей чисел P и N совпадают
(состав числа - это множество цифр, из которых состоит его запись)
Числа 1331 и 13 имеют одинаковый состав, а числа 101 и 11 разный

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

# Для задачи 1
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] == 1 :
      dd, d2 = d * d, 2 * d
      M[dd :N :d2] = [0]* len(range(dd, N, d2))
  return M  
def check_1(p) :
  s2 = set(int(a) for a in str(p))
  s1 = set(int(a) for a in str(p * p))
  return s1 == s2
  
A, B = 10**14, 10**15
t0 =prt()
a, b = int(A**0.5), int(B**0.5) + 1
while ( a * a < A) : a += 1
while ( b * b > B) : b -= 1
print(f'{a=} {b=}')
P = sieve(b+1)
X = [i for i in range(a,b+1) if P[i] and check_1(i) ]
Y = [(p, p * p) for p in X]
K = len(X)
print(f'На отрезке [{A};{B}] обнаружено {K} подходящих чисел. time = {prt() - t0}')
#for xy in Y :
#  print(xy[1], xy[0])
print(len(X), sum(X))

Задача 2 Числа с одним собственным делителем и совпадающие с ним по составу

Напишите программу, которая на отрезке [A; B] находит все "особые" числа отрезка.
Число N называется "особым", если выполнены следующие условия:

число N имеет один собственный делитель P
(собственный делитель, это делитель отличный от 1 и самого числа)
десятичная запись собcственного делителя P состоит из неповторяющихся цифр
(число 1234567 состоит из неповторяющихся цифр, а число 131 нет)
составы десятичных записей чисел P и N совпадают
(состав числа - это множество цифр, из которых состоит его запись)
Числа 1331 и 13 имеют одинаковый состав, а числа 101 и 11 разный

# Для задачи 2
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] == 1 :
      dd, d2 = d * d, 2 * d
      M[dd :N :d2] = [0]* len(range(dd, N, d2))
  return M  
def check_2(p) :
  s2 = set(int(a) for a in str(p))
  if len(s2) < len(str(p)) : return False
  s1 = set(int(a) for a in str(p * p))
  return s1 == s2
  
A, B = 247*10**13, 25*10**14
t0 =prt()
a, b = int(A**0.5), int(B**0.5) + 1
while ( a * a < A) : a += 1
while ( b * b > B) : b -= 1
print(f'{a=} {b=}')
P = sieve(b+1)
X = [i for i in range(a,b+1) if P[i] and check_2(i) ]
Y = [(p, p * p) for p in X]
K = len(X)
print(f'На отрезке [{A};{B}] обнаружено {K} подходящих чисел. time = {prt() - t0}')
for xy in Y :
  print(xy[1], xy[0])

Задача 3 Числа с тремя собственными делителями, совпадающими по составу

Напишите программу, которая на отрезке [A; B] находит все "неуловимые" числа отрезка.
Число N называется "неуловимым", если выполнены следующие условия:

число N имеет три собственных делитель a, b, c
(собственный делитель, это делитель отличный от 1 и самого числа)
составы десятичных записей чисел a, b, c совпадают
(состав числа - это множество цифр, из которых состоит его запись)
Числа 1331 и 13 имеют одинаковый состав, а числа 101 и 11 разный

# Для задачи 3
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] == 1 :
      dd, d2 = d * d, 2 * d
      M[dd :N :d2] = [0]* len(range(dd, N, d2))
  return M  
def check_1(p) :
  s1 = set(int(a) for a in str(p))
  pp = p * p
  s2 = set(int(a) for a in str(pp))
  if s1 != s2 : return False
  s3 = set(int(a) for a in str(pp * p))
  return s1 == s3
  
A, B = 1, 10**30
t0 =prt()
a, b = int(A**0.25), int(B**0.25) + 1
while ( a ** 4 < A) : a += 1
while ( b ** 4 > B) : b -= 1
print(f'{a=} {b=}')
P = sieve(b+1)
X = [i for i in range(a,b+1) if P[i] and check_1(i) ]
Y = [(p, p ** 2, p ** 3, p ** 4) for p in X]
K = len(X)
print(f'На отрезке [{A};{B}] обнаружено {K} подходящих чисел. time = {prt() - t0}')
for xy in Y :
  print(* xy)
#print(len(X), sum(X))

Печать