Задание 25. Информатика. 2023-17
- Просмотры: 568
- Изменено: 25 ноября 2024
Напишите программу, которая перебирает целые числа, большие \(650~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 = 650001
k = 0
while k < 6:
md = max_divisor(n)
if md < n and not is_prime(md):
print(n, md)
k += 1
n += 1
Ответ:
\(650001\) \(216667\)
\(650003\) \(28261\)
\(650004\) \(325002\)
\(650005\) \(130001\)
\(650006\) \(325003\)
\(650007\) \(216669\)