Поиск дружественных пар чисел с помощью циклов
Составьте программу для решения задачи. Два натуральных числа называются дружественными, если каждое из них равно сумме всех делителей другого (само другое число в качестве делителя не рассматривается). Например, 220 (1+2+4+5+10+11+20+22+44+55+110=284) и 284 (1+2+4+71+142=220) – дружественные числа. Пары необходим о выводить по одной в строке, разделяя пробелами. Найти все пары натуральных дружественных чисел, меньших 10 000.
Решения на эту задачу уже есть в интернете, но, насколько я понял, они с употреблением массивов, что мне не подходит. Я хотел бы сделать эту задачу только при использовании циклов, вроде у меня и получилось:
for i in range(1, 9999):
for k in range(1, i // 2 + 1):
if i % k == 0:
sum1 += k
for j in range(i + 1, 9999):
if j == i:
continue
for k in range(1, j // 2 + 1):
if j % k == 0:
sum2 += k
if sum1 == j and sum2 == i:
print(i, j, sep=' ')
sum1, sum2 = 0, 0
Но решение настолько долгое, что я не хочу ждать даже вторую пару чисел. Пожалуйста, помогите с оптимизацией.
Ответы (2 шт):
такое решение вас устраивает?
def getSum(value):
res = 1
for i in range(2, int(value**0.5) + 1):
if value % i == 0:
res += i + value // i
return res
for i in range(10, 10000):
sum1 = getSum(i)
sum2 = getSum(sum1)
if sum2 == i and sum1 != sum2:
print(i, sum1)
вычисление суммы множителей выполняется максимально быстро (скорость sqrt(N))
т.е. чтобы найти все делители не надо проходить от 1 до N / 2, достаточно пройти от 2 до sqrt(N) найдя 2 делителя - основной и второй, который равен частному от числа и найденного основного делителя
специально не выводятся такие числа как 28 (число равно сумму делителей)
недостаток - будут дубликаты (без списков эту проблему не решить), т.е. будет найдено 220 284 и 284 220
Можно использовать функцию sum, но тогда неявно все таки используются списки:
for value in range(10, 10000):
sum1 = 1 + sum((i + value // i) for i in range(2, int(value**0.5) + 1) if value % i == 0)
sum2 = 1 + sum((i + sum1 // i) for i in range(2, int(sum1**0.5) + 1) if sum1 % i == 0)
if sum2 == value and sum1 != sum2:
print(value, sum1)
P.S.
кстати правильнее обрабатывать по другому полные квадраты, ведь по приведённому выше алгоритму корень как множитель складывается 2 раза
def getSum(value):
res = 1 + (0 if int(value**0.5)**2 != value else int(value**0.5))
for i in range(2, int(value ** 0.5)):
if value % i == 0:
res += i + value // i
return res
теперь для 25 вместо неправильных 11 выдается правильные 6
Вы перебираете все пары чисел 1 <= i < j < 10000 и проверяете что sum_of_proper_divisors(i) = sum_of_proper_divisors(j). Технически это правильный способ, но как долго это будет работать? Я взял вашу программу и сделал из неё считалку итераций:
c = 0
for i in range(1, 9999):
for k in range(1, i // 2 + 1):
c += 1
for j in range(i + 1, 9999):
c += j // 2
print(c)
$ python count-ops.py 166579182499
167 миллиардов операций. Мой компьютер делает около 10 миллионов итераций в секунду. 16700 секунд - ожидаемое время работы вашего кода.
Вместо двух циклов достаточно одного по i. Второе число вычисляется как j = sum_of_proper_divisors(i). Ещё одно вычисление нужно чтобы проверить второе соотношение - i == sum_of_proper_divisors(j). На вскидку, так будет в 10000 раз меньше итераций. Проверяем:
def sum_of_proper_divisors(n):
s = 0
for k in range(1, n // 2 + 1):
if n % k == 0:
s += k
return s
for i in range(1, 10000):
j = sum_of_proper_divisors(i)
if i < j <= n and i == sum_of_proper_divisors(j):
print(i, j)
$ time python amicable-numbers.py 220 284 1184 1210 2620 2924 5020 5564 6232 6368 real 0m1.582s user 0m1.576s sys 0m0.004s
Ваша задача решена. Идем дальше.
NB: range(?, 9999) исключает 9999 из цикла. Вам повезло, это не влияет на результат, но цикл должен быть длиннее на единицу.
Если к сумме которую мы считаем добавить n, то получится сумма всех делителей числа n (любое число делится само на себя, но мы этот делитель не учитываем). Для суммы всех делителей есть функция делителей. Статья про неё написана несколько сложно, но разобраться при желании можно. Сумму всех делителей числа можно выразить как произведение некоторых множителей, которые зависят от разложения этого числа на простые. Получается такая пара функций:
def sum_of_divisors(n):
s = 1
i = 2
j = n
j_sqrt = math.isqrt(j)
while i <= j_sqrt:
if j % i == 0:
f = 1
m = 1
while j % i == 0:
j //= i
m *= i
f += m
j_sqrt = math.isqrt(j)
s *= f
i += 1
if j > 1:
s *= j + 1
return s
def sum_of_proper_divisors(n):
return sum_of_divisors(n) - n
Получается сложнее чем ваш вариант, зато быстрее. Кроме того это факультатив.
$ time python amicable-numbers.py 220 284 1184 1210 2620 2924 5020 5564 6232 6368 real 0m0.066s user 0m0.064s sys 0m0.004s
66 миллисекунд, из них 25 - загрузка программы в память.
16 секунд для миллиона:
$ time python amicable-numbers-1000000.py 220 284 1184 1210 2620 2924 ... 802725 863835 879712 901424 898216 980984 real 0m15.282s user 0m15.276s sys 0m0.004s
Условия вопроса запрещают использовать списки. Со списками можно было бы сделать решето Эратосфена с которым задача для миллиона решается за полторы секунды, а для десяти миллионов за шестнадцать секунд.