Как ускорить программу?
Два различных натуральных числа называются дружественными, если первое из них равно сумме делителей второго числа, за исключением самого второго числа, а второе равно сумме делителей первого числа, за исключением самого первого числа. Требуется найти все пары дружественных чисел, оба из которых принадлежат промежутку от 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')
Однако в системе на одном из тестов не заходит по времени, как ускорить программу?
Ответы (4 шт):
первая итерация - вычислить сначала сумму делителей и только потом с ними работать
n = 10000
# получить соответствие число - делитель
numbers = [0,]
for value in range(1, n):
dividers = 1
for i in range(2, value):
if value % i == 0:
dividers += i
numbers.append(dividers)
# вывести все пары дружественных чисел
for value1 in range(1, n):
for value2 in range(1, value1 + 1):
if value1 == numbers[value2] and value2 == numbers[value1]:
print(value1, value2)
при этом рассматривать не все пары чисел, а только пары в которых первое число больше или равно второму (чтобы избежать дублирование пар) - тогда будет выполняться всего n^2 / 2 действий
при этом самое долгое в данном алгоритме - вычисление делителей
про n=1000000 говорить не приходится (будет очень долго считаться, минуты)
вторая итерация - нет надобности проверять все делители от 2 до n, достаточно определять делители от 2 до n / 2 - это ускоряет алгоритм в 2 раза:
# получить соответствие число - делитель
numbers = [0,]
for value in range(1, n):
dividers = 1
for i in range(2, value // 2 + 1):
if value % i == 0:
dividers += i
numbers.append(dividers)
итерация №3 - алгоритм поиска суммы делителей можно немного ускорить (в полтора-два раза) если переписать код через функции питона (не знаю почему так получается):
for value in range(1, n):
dividers = 1 + sum(i for i in range(2, value // 2 + 1) if value % i == 0)
numbers.append(dividers)
можно свернуть в чуть более короткий код (но такая же скорость работы)
# получить соответствие число - делитель
numbers = [(1 + sum(i for i in range(2, value // 2 + 1) if value % i == 0)) for value in range(1, n)]
итерация №4 - делители можно рассматривать до sqrt(value), но тогда необходимо дополнительно учитывать и вторые делители - value // i:
for value in range(1, n):
dividers = 1 + sum((i + value // i) for i in range(2, int(math.sqrt(value)) + 1) if value % i == 0)
numbers.append(dividers)
или
numbers = [(1 + sum((i + value // i) for i in range(2, int(math.sqrt(value)) + 1) if value % i == 0)) for value in range(1, n)]
Статья Функция делителей рассказывает как по разложению числа на простые найти сумму его делителей. Это один из самых быстрых способов.
Разложить ряд последовательных целых чисел на простые множители можно быстрее, чем раскладывать их по отдельности. Почти всё время уходит на проверку делимости. А проверить делимость группы чисел можно так же быстро, как проверить делимость одного числа. Совокупный выигрыш очень велик.
sigma1(n1, n2) - возвращает список сумм делителей чисел из диапазона [n1, n2). amicables(n1, n2) использует этот список, чтобы отыскать пары дружественных чисел.
import math
def sigma1(n1, n2):
ss = [1] * (n2 - n1)
ns = list(range(n1, n2))
p = 2
for i in range(-n1 % p, n2 - n1, p):
ns[i] //= p
m = p
f = 1 + p
while ns[i] % p == 0:
ns[i] //= p
m *= p
f += m
ss[i] *= f
for p in range(3, math.isqrt(n2 - 1) + 1, 2):
i1 = -n1 % p
if i1 >= n2 - n1 or ns[i1] % p != 0:
continue
for i in range(i1, n2 - n1, p):
ns[i] //= p
m = p
f = 1 + p
while ns[i] % p == 0:
ns[i] //= p
m *= p
f += m
ss[i] *= f
for i in range(n2 - n1):
if ns[i] > 1:
ss[i] *= ns[i] + 1
return ss
def amicables(n1, n2):
ss = sigma1(n1, n2)
for i in range(n1, n2):
j = ss[i - n1] - i
if i < j < n2 and i == ss[j - n1] - j:
yield i, j
def main():
m, n = map(int, input().split())
absent = True
for i, j in amicables(m, n + 1):
print(i, j)
absent = False
if absent:
print('Absent')
main()
Полторы секунды до миллиона:
$ time echo 1 1_000_000 | python amicables.py 220 284 1184 1210 2620 2924 5020 5564 6232 6368 10744 10856 12285 14595 17296 18416 63020 76084 66928 66992 67095 71145 69615 87633 79750 88730 100485 124155 122265 139815 122368 123152 141664 153176 142310 168730 171856 176336 176272 180848 185368 203432 196724 202444 280540 365084 308620 389924 319550 430402 356408 399592 437456 455344 469028 486178 503056 514736 522405 525915 600392 669688 609928 686072 624184 691256 635624 712216 643336 652664 667964 783556 726104 796696 802725 863835 879712 901424 898216 980984 real 0m1.385s user 0m1.356s sys 0m0.028s
Не знаю, устроит или нет. Есть ещё и очень короткий вариант кода, но он работает существенно медленнее, чем этот. Этот вариант не сильно отличается от исходного:
import os
import math
def sd(k):
s = 0
m = int(math.sqrt(k))
for i in range(1, m + 1):
if k % i == 0:
if i * i == k: s += i
else: s += i + k // i
return s - k
a = input("Введите два числа: ").split()
n, m = int(a[0]), int(a[1])
f = False
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 = True
if not f: print("Absent")
print("\nНажмите любую клавишу для продолжения...")
os.system("pause > nul" if os.name == "nt" else "read > /dev/null")
Простейшее решение – просто суммировать делители:
0 1 2 3 4 5 6 7 8 9 10 11 12 # индексы 1 1 1 1 1 1 1 1 1 1 1 # единицу добавим ко всем > 1 2 2 2 2 2 # двойку добавим ко всем четным > 2 3 3 3 # тройку аналогично 4 4 5 6 0 0 1 1 3 1 6 1 7 4 8 1 16 # сумма всех делителей числа # меньших него самого
Простая идея рождает простую программу:
m, n = map(int, input().split())
n += 1
s = [0] * n
for i in range(1, (n + 1) // 2):
for j in range(2 * i, n, i):
s[j] += i
absent = True
for i in range(m, n):
j = s[i]
if i < j < n and s[j] == i:
print(i, j)
absent = False
if absent:
print('Absent')
Работает быстро: сложность O(n·log n). 3.5 секунды до миллиона:
$ time echo 1 1_000_000 | python amicables.py 220 284 1184 1210 2620 2924 5020 5564 6232 6368 10744 10856 12285 14595 17296 18416 63020 76084 66928 66992 67095 71145 69615 87633 79750 88730 100485 124155 122265 139815 122368 123152 141664 153176 142310 168730 171856 176336 176272 180848 185368 203432 196724 202444 280540 365084 308620 389924 319550 430402 356408 399592 437456 455344 469028 486178 503056 514736 522405 525915 600392 669688 609928 686072 624184 691256 635624 712216 643336 652664 667964 783556 726104 796696 802725 863835 879712 901424 898216 980984 real 0m3.425s user 0m3.412s sys 0m0.008s