Задание 25 ЕГЭ по информатике 2022 года относится к задачам высокого уровня сложности, на его выполнение отводится около 20 минут. В 2022 году за правильное решение начислялся один первичный балл. Задание предполагает обработку целых чисел и проверку делимости. Ниже приведен разбор нескольких вариантов решения на языке Python.
Поиск делителей числа
Рассмотрим алгоритм поиска делителей числа. Пусть требуется найти все делители числа x = 36. Простой подход — перебор всех чисел от 1 до x включительно:
x = 36
devs = []
for i in range(1, x + 1):
if x % i == 0:
devs.append(i)
print(devs)Этот метод эффективен для небольших чисел, но для больших чисел становится слишком медленным. Для ускорения процесса можно использовать тот факт, что наименьший делитель из пары делителей не превышает квадратного корня из числа. Таким образом, достаточно перебирать числа до $sqrt{x}$:
import math
x = 36
devs = set() # Используем множество для исключения дубликатов
for i in range(1, int(math.sqrt(x)) + 1):
if x % i == 0:
devs.add(i)
devs.add(x // i)
print(sorted(list(devs))) # Преобразуем множество в отсортированный список для выводаЭтот оптимизированный алгоритм значительно быстрее, особенно при работе с большими числами.
Задачи
Задача 1: Числа с ровно четырьмя делителями
Напишите программу, которая находит среди целых чисел в диапазоне от 338472 до 338490 (включительно) числа, имеющие ровно четыре различных делителя. Для каждого найденного числа выведите два наибольших делителя в порядке возрастания.
import math
for x in range(338472, 338491):
devs = set()
for i in range(1, int(math.sqrt(x)) + 1):
if x % i == 0:
devs.add(i)
devs.add(x // i)
if len(devs) == 4:
sorted_devs = sorted(list(devs))
print(sorted_devs[-2], sorted_devs[-1])Задача 2: Числа с ровно пятью делителями
Напишите программу, которая ищет среди целых чисел в диапазоне от 136 до 143 (включительно) числа, имеющие ровно пять различных делителей. В ответе для каждого найденного числа запишите два наибольших делителя, не равных самому числу, в порядке возрастания.
import math
for x in range(136, 144):
devs = set()
for i in range(1, int(math.sqrt(x)) + 1):
if x % i == 0:
devs.add(i)
devs.add(x // i)
if len(devs) == 5:
sorted_devs = sorted(list(devs))
print(sorted_devs[-2], sorted_devs[-1])Задача 3: Поиск простых чисел
Напишите программу, которая ищет среди целых чисел в диапазоне от 8551 до 717866 (включительно) простые числа. Выведите все найденные простые числа в порядке возрастания, слева от каждого числа укажите его номер по порядку.
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
count = 0
for num in range(8551, 717867):
if is_prime(num):
count += 1
print(f"{count}. {num}")Задача 4: Числа с двумя простыми делителями
Рассматриваются целые числа в диапазоне от 631632 до 684935 (включительно), которые являются произведением двух различных простых чисел. Найдите среди них число, у которого два простых делителя наиболее сильно отличаются друг от друга. Выведите эти два делителя.
import math
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
max_diff = 0
result = None
for x in range(631632, 684936):
for i in range(2, int(math.sqrt(x)) + 1):
if x % i == 0 and is_prime(i) and is_prime(x // i) and i != x // i:
diff = abs(i - (x // i))
if diff > max_diff:
max_diff = diff
result = (i, x // i)
print(min(result), max(result))Задача 5: Числа вида 2<sup>m</sup> * 3<sup>n</sup>
Найдите все натуральные числа n в диапазоне от 150 000 000 до 300 000 000, которые можно представить в виде 2<sup>m</sup> * 3<sup>n</sup>, где m — нечётное число, n — чётное число. Запишите все найденные числа в порядке возрастания, справа от каждого числа укажите сумму m + n.
numbers = []
for m in range(1, 1000, 2):
for n in range(0, 1000, 2):
num = 2**m * 3**n
if 150000000 <= num <= 300000000:
numbers.append((num, m + n))
numbers.sort()
for num, sum_mn in numbers:
print(f"{num} ({sum_mn})")Задача 6: Числа с наибольшим не простым делителем
Напишите программу, которая перебирает целые числа, большие 500000, в порядке возрастания и ищет среди них такие, для которых наибольший натуральный делитель (не равный самому числу) не является простым числом. Программа должна найти и вывести первые шесть таких чисел и соответствующие им значения упомянутых делителей.
def is_prime(n):
if n < 2:
return False
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
count = 0
num = 500001
while count < 6:
largest_non_prime_divisor = 1
for i in range(2, num):
if num % i == 0 and not is_prime(i):
largest_non_prime_divisor = max(largest_non_prime_divisor, i)
if largest_non_prime_divisor > 1:
count += 1
print(f"{num} {largest_non_prime_divisor}")
num += 1В статье были рассмотрены различные варианты решения 25 задания ЕГЭ по информатике, демонстрирующие различные подходы к обработке чисел и поиску делителей. Ключевыми моментами являются оптимизация алгоритмов поиска делителей (использование квадратного корня) и эффективное использование множеств для удаления дубликатов. Понимание этих принципов поможет успешно справиться с подобными задачами на экзамене.