Задание 25. Информатика. ЕГЭ. Шастин. 4.10.2024
- Просмотры: 251
- Изменено: 24 ноября 2024
(Д. Бахтиев) Напишите программу, которая перебирает целые числа, большие \(1~000~000\), в порядке возрастания и ищет среди них те, которые имеют ровно \(3\) простых делителя. В ответе запишите \(5\) наименьших таких чисел в порядке возрастания. Справа от каждого такого числа укажите его наибольший простой делитель.
Количество строк в таблице для ответа избыточно.
Решение:
Python
def is_prime(n):
if n == 2 or n == 3:
return True
for x in range(2, int(n**0.5) + 1):
if n % x == 0:
return False
return True
def prime_divisors(n):
divisors = set()
for x in range(2, int(n**0.5) + 1):
if n % x == 0:
divisors.add(x)
divisors.add(n // x)
return [p for p in divisors if is_prime(p)]
i = 0
x = 1_000_000
while i < 5:
x += 1
d = prime_divisors(x)
if len(d) == 3:
print(x, max(d))
i += 1
Ответ:
\(1000002\) \(166667\)
\(1000004\) \(89\)
\(1000006\) \(71429\)
\(1000012\) \(19231\)
\(1000013\) \(383\)