Задание 25. Информатика. 2023-15
- Просмотры: 66
- Изменено: 21 ноября 2024
Напишите программу, которая перебирает целые числа, большие \(450~000\), в порядке возрастания и ищет среди них такие, для которых наибольший натуральный делитель, не равный самому числу, не является простым числом. Программа должна найти и вывести первые \(6\) таких чисел и соответствующие им значения упомянутых делителей.
Формат вывода: для каждого из \(6\) таких натуральных чисел в отдельной строке сначала выводится само число, затем упомянутый делитель. Строки выводятся в порядке возрастания найденных чисел.
Например, для числа \(105\) наибольший натуральный делитель \(35\) не является простым, для числа \(15\) наибольший натуральный делитель \(5\) — простое число, а для числа \(13\) такого делителя не существует.
Решение:
Python
def is_prime(n: int) -> bool:
if n == 1:
return False
if n in (2, 3):
return True
for x in range(2, int(n**0.5)+1):
if n % x == 0:
return False
return True
def min_divisor(n: int) -> int:
for x in range(2, int(n**0.5) + 1):
if n % x == 0:
return x
return 1
def max_divisor(n: int) -> int:
return n // min_divisor(n)
n = 450001
k = 0
while k < 6:
md = max_divisor(n)
if md < n and not is_prime(md):
print(n, md)
k += 1
n += 1
Ответ:
\(450002\) \(225001\)
\(450004\) \(225002\)
\(450006\) \(225003\)
\(450007\) \(26471\)
\(450008\) \(225004\)
\(450009\) \(150003\)