Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [13194; 22052], пары взаимно простых чисел, имеющих ровно четыре различных натуральных делителя, не считая единицы и самого числа, и выводит на экран такую пару с наибольшей суммой элементов. В ответе укажите элементы этой пары через пробел в порядке возрастания.
mx = 0 # Макс. сумма
mxe = () # Элементы с макс. суммой
# Идём с самых больших чисел, чтобы быстрее найти пару с максимальной суммой
for i in range(22052, 13193, -1):
d1 = set() # Делители первого числа
for j in range(i-1, 13193, -1):
# Если пара не больше текущего максимума, то рассматривать её нет смысла
if i+j < mx:
break
f = 0
d2 = set() # Делители второго числа
for d in range(2, int(j**0.5)+1):
# Если делители совпадают, то пропускаем пару
if i % d == 0 and j % d == 0:
f = 1
break
# Добавляем делители в множества
if i % d == 0:
d1.add(d)
d1.add(i//d)
if j % d == 0:
d2.add(d)
d2.add(j//d)
# Если числа не имеют общих делителей и их по 4, то засчитываем
if f == 0 and len(d1) == 4 and len(d2) == 4:
if i+j > mx:
mx = i+j
mxe = (j, i)
# Прерываем цикл, потому что дальше числа поменьше
break
print(mxe)
Ответ: 22025 22028