Задание 25. Информатика. 2023-19
Пусть \(S\) — сумма различных натуральных делителей целого числа, являющихся простыми числами, не считая самого числа.
Напишите программу, которая перебирает целые числа, большие \(550~000\), в порядке возрастания и ищет среди них такие, для которых значение \(S\) оканчивается на цифру \(1\). Программа должна найти и вывести первые \(5\) таких чисел и соответствующие им значения \(S\).
Формат вывода: для каждого из \(5\) таких найденных чисел в отдельной строке сначала выводится само число, затем значение \(S\). Строки выводятся в порядке возрастания найденных чисел.
Например, для числа \(20\) \(S = 2 + 5 = 7\).
Решение:
Python
def divisors(n: int) -> set[int]:
s = set()
for x in range(2, int(n**0.5)+1):
if n % x == 0:
s.add(x)
s.add(n//x)
return s
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 prime_divisors(n: int) -> set[int]:
div = divisors(n)
if div:
return set(filter(is_prime, div))
n = 550001
k = 0
while k < 5:
if pd := prime_divisors(n):
S = sum(pd)
if S % 10 == 1:
print(n, S)
k += 1
n += 1
Ответ:
\(550023\) \(1461\)
\(550025\) \(461\)
\(550030\) \(4251\)
\(550043\) \(1501\)
\(550045\) \(4811\)