Задание 25. Информатика. 2023-18
Напишите программу, которая перебирает целые числа, большие \(750~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 = 750001
k = 0
while k < 6:
md = max_divisor(n)
if md < n and not is_prime(md):
print(n, md)
k += 1
n += 1
Ответ:
\(750001\) \(107143\)
\(750002\) \(375001\)
\(750003\) \(250001\)
\(750004\) \(375002\)
\(750006\) \(375003\)
\(750008\) \(375004\)