(Р.Косов ITец) Напишите программу, которая перебирает целые числа, меньшие 5 800 000, в порядке убывания и ищет среди них те, которые можно представить в виде произведения квадрата трёхзначного числа и простого числа.
В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке убывания, а во втором столбце - для каждого числа соответствующее простое число.
Количество строк в таблице для ответа избыточно.
Решение
🔹 Шаг 1. Идея решения
📌
Перебираем числа больше 13475124 и ищем те, которые раскладываются в произведение 5 простых множителей, и каждый простой множитель содержит цифру 5 в записи.
Во втором столбце выводим наибольший из множителей.
🔹 Шаг 2. Проверка простоты
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
📌 Функция is_prime используется при разложении на множители.
🔹 Шаг 3. Перебор чисел и вывод ответа
c = 0
for x in range(5_799_999, 0, -1):
for d in range(2, int(x ** 0.5) + 1):
if x % d == 0:
q = x // d
r = int(q ** 0.5)
if is_prime(d) and r * r == q and 100 <= r <= 999:
print(x, d)
c += 1
break
r = int(d ** 0.5)
if r * r == d and 100 <= r <= 999 and is_prime(x // d):
print(x, x // d)
c += 1
break
if c == 5:
break
📌
Если длина списка множителей равна 5, число подходит — выводим его и наибольший множитель.
Останавливаемся после 5 найденных чисел.
