Задача 9 (Excel) в 2023 г.

Задача про сумму делителей

На сайте Полякова приводится следующая задача (задача 25 из варианта 4):

(№ 4211) (А. Комков) Обозначим через S сумму делителей числа, не являющихся простыми, кроме единицы и самого числа. Если таких делителей у числа нет, то S равно нулю. Напишите программу, которая перебирает нечетные целые числа, меньшие 912673, в порядке убывания и ищет среди них первые 5 чисел, которые кратны S. Для каждого из найденных чисел в отдельной строке сначала выводится само число, затем значение S. Строки выводятся в порядке убывания найденных чисел. 

Воспользуемся для решения этой задачи алгоритмами разложения числа на множители и проверки чисел на простоту, подробно описанными в статье Разложение на множители и простые числа.

Напишем функцию, вычисляющую значение S:

def S(n):
    d = divisors(n)
    s=0
    for i in range(len(d)):
        if not isprime(d[i]): s += d[i]
    return s

Эта функция использует функцию divisors, возвращающую массив делителей числа, и функцию isprime, проверяющую, является ли число простым.

Основная программа - достаточно короткая: в цикле проверяются нечетные числа, меньшие чем 912673 (т.е. начинаем с числа 912671). Для каждого числа вычисляется функция S, и если она не равна нулю и число ей кратно, то печатается число и значение S. Когда будет найдено 5 чисел, программа завершает работу.

Приведем текст программы целиком:

def isprime(n):
    k=2
    while k*k <= n:
        if n%k == 0: return False
        k += 1
    return True
    
def divisors(n):
    d=[]
    k=2
    while k*k <= n:
        if n%k == 0:
            d.append(k)
            k2 = n//k
            if k2 > k: d.append(k2)
        k += 1
    return d

def S(n):
    d = divisors(n)
    s=0
    for i in range(len(d)):
        if not isprime(d[i]): s += d[i]
    return s
    
n=912671
k=0
while k<5:
    sn=S(n)
    if sn > 0:
        if n%sn == 0:
            print(n,sn)
            k += 1
    n -= 2

Программа находит решение примерно за полминуты: не слишком быстро, но приемлемо.

Результат работы программы следующий:

704969 7921
571787 6889
493039 6241
389017 5329
357911 5041

Он совпадает с ответом, приведенным у Полякова.

Интересно, что все найденные числа являются кубами простых чисел  89, 83, 79, 73, 71 соответственно. Если вы можете доказать, что число может быть кратно функции S только в том случае, если оно является кубом простого числа - то вы можете написать сверхэффективную программу, которая находит простые числа, кубы которых меньше 912671, и печатает кубы и квадраты этих чисел.

Вот программа, реализующая данную идею:

def isprime(n):
    k=2
    while k*k <= n:
        if n%k == 0: return False
        k += 1
    return True
    
n=99
k=0
while k<5:
    if isprime(n):
        if n**3 < 912673:
            print(n**3,n**2)
            k += 1
    n -= 2 

Программа выдает тот же самый результат, но выполняется не за полминуты, а примерно за 5 миллисекунд, т.е. в несколько тысяч раз быстрее. Но, повторюсь, перед её использованием надо доказать, что указанным в задаче свойством могут обладать только кубы простых чисел. 

(c) Ю.Д.Красильников, 2021 г.