Назовём простым числом такое натуральное число, которое имеет ровно два различных натуральных делителя — единицу и само число.
Назовём нетривиальным делителем числа X такой натуральный делитель числа X, который отличен от 1 и от самого числа.
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [170 000; 180 000], числа, у которых максимальный нетривиальный делитель является квадратом простого числа. Для каждого найденного числа запишите самый маленький и самый большой нетривиальный делитель в порядке возрастания произведения этих двух делителей. Делители в строке должны следовать в порядке возрастания.
# функция проверки число на простое
def prost(n):
if n == 1:return False
for i in range(2, int(n**0.5)+1):
if n % i == 0:
return False
return True
# функция поиска нетривиальных делителей
def find_divs(n):
divs = set() # Множество для хранения делителей
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0: # Если i делитель n
divs.add(i) # Добавляем i в множество делителей
divs.add(n // i) # Добавляем парный делитель
return sorted(divs) # Возвращаем отсортированный список делителей числа n
for i in range(170000, 180000 + 1):
d = find_divs(i)
if len(d) > 0: # если у числа есть нетривиальные делители
if d[-1]**0.5 == int(d[-1]**0.5) and prost(d[-1]**0.5): # проверяем, что макс. нетривиальный делитель - квадрат простого числа
print(d[0],d[-1]) # вывод минимального и максимального нетривиального делителя
Ответ: 3 57121 2 85849 7 24649 17 10201 3 58081 47 3721 11 16129 19 9409