Задание 25. Информатика. 2023-19

Просмотры: 701
Изменено: 1 февраля 2025

Пусть 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