Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [7123; 19234], пары взаимно простых чисел, имеющих ровно два различных натуральных делителя, не считая единицы и самого числа, и выводит на экран такую пару с наибольшей суммой элементов. В ответе укажите элементы этой пары через пробел в порядке возрастания.
Примечание: взаимно простые числа — это два числа, у которых наибольший общий делитель равен единице. Другими словами, у взаимно простых чисел нет общих делителей, кроме единицы. Например, числа 7 и 12 являются взаимно простыми, так как их наибольший общий делитель равен единице, в то время как числа 8 и 12 не являются взаимно простыми, так как их наибольший общий делитель равен 4.
def count_div(number): # функция, которая считает кол-во делителей числа
count = 0
for div in range(2, int(number ** 0.5) + 1):
if number % div == 0:
count += 1
if div != number // div:
count += 1
if count > 2: # для оптимизации выходим из цикла если делителей больше 2 - такие числа нам не подходят
break
return count
def gcd(a, b): # рекурсивная функция реализующая алгоритм Евклида. Вместо данной функции можно использовать функции gcd из модуля math
if b > a:
return gcd(b, a)
if b != 0:
return gcd(b, a % b)
return a + b
max_summ = 0
x, y = 0, 0
# для оптимизации делаем переборы от большего к меньшему, так как нам нужно указать максимальную сумму в ответ
for i in range(19234, 7122, -1): # перебор первого числа пары
for j in range(i - 1, 7122, -1): # перебор второго числа пары
if i + j > max_summ:
if gcd(i, j) == 1: # если НОД пары равен 1
if count_div(i) == 2 and count_div(j) == 2: # если у каждого ровно по 2 нетривиальных делителя
max_summ = i + j
x = j
y = i
else:
break
print(x, y)
Ответ: 19223 19226