Python-сообщество

Два различных натуральных числа называются дружественными, если первое из них равно сумме делителей второго числа, за исключением самого второго числа, а второе равно сумме делителей первого числа, за исключением самого первого числа. Требуется найти все пары дружественных чисел, оба из которых принадлежат промежутку от M до N.

Входные данные
В первой строке находятся числа M и N. 1 <= M <= N <= 1 000 000, все числа целые.

Выходные данные
В каждой строке вывести по паре чисел через пробел. Первое число пары должно быть меньше второго. Строки должны быть отсортированы в порядке возрастания первого числа пары. Если пар дружественных чисел в промежутке нет, вывести “Absent”.

 def sd(k):
    s = 0
    m = int(k**0.5)
    for i in range(1, m+1):
        if k%i == 0:
            if i**2 == k:
                s += i    
            else:
                s+=i
                s+=(k//i)
    s -= k
    return s
a = input().split()
n,m = int(a[0]), int(a[1])
f = 0
for i in range(n, m):
    for j in range(i+1, m+1):
        if sd(i) == j and sd(j) == i:
            print(i, j)
            f = 1
if f == 0:
    print('Absend')

Отредактировано Fiares_Curie (Окт. 28, 2021 14:40:12)

Fiares_Curie
Очевидно, ваш алгоритм не оптимален. Вообще, мне кажется, что вы решаете задачу “в лоб”, ровно как написано. Вы для каждого i перебираете диапазон и проверяете условие(i, j) то есть ваш алгоритм имеет квадратичную сложность (для n значений вам надо выполнить n**2 вычислений). Я бы делал не так, вы можете для каждого i из диапазона не искать соответсвующие дружественные числа в том же диапазоне, а вычислить все его дружественные числа и отсеять те из них, которые попадают в диапазон.

Fiares_Curie
Программа не заходит в системе на одном из тестов по времени. Что не так?