Задание 25. Информатика. 2023-16
- Просмотры: 86
- Изменено: 25 ноября 2024
Напишите программу, которая перебирает целые числа, большие \(350~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 = 350001
k = 0
while k < 6:
md = max_divisor(n)
if md < n and not is_prime(md):
print(n, md)
k += 1
n += 1
Ответ:
\(350001\) \(116667\)
\(350002\) \(175001\)
\(350004\) \(175002\)
\(350007\) \(116669\)
\(350008\) \(175004\)
\(350009\) \(31819\)