Дружественные числа до 10000

@opdfpg · Регистрация: 13.05.2015

Студворк — интернет-сервис помощи студентам

Здравствуйте. Помогите с задачкой: Найти все пары дружественных чисел до 10 000. Пара дружественных чисел - это два различных натуральных числа, для которых сумма всех делителей первого числа равна второму числу и наоборот, сумма всех делителей второго числа равна первому числу. Например, 220 и 284 (делители для 220 это 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, сумма делителей равна 284. Делители для 284 это 1, 2, 4, 71 и 142, сумма которых равна 220).

@TroSer · 13.05.2015, 18:14

Сообщение от opdfpg

Делители для 284 это 1, 2, 4, 71 и 142

Мне кажется, если 1 является делителем числа 284 то и 284 - делитель 284?

Python
1
2
3
4
5
6
7
8
9
10
11
12
limit = 10000
pairs = {}
    
def divisors_sum(number):
    return sum(x for x in range(1, (number//2)+1) if number%x == 0)
    
for i in range(1, limit+1):
    aggr = divisors_sum(i)
    if i == divisors_sum(aggr) and i != aggr :
        if i and aggr not in pairs:
            pairs[i] = aggr
print(pairs)

Python
1
{1184: 1210, 2620: 2924, 5020: 5564, 220: 284, 6232: 6368}

p.s. Было бы неплохо, если бы кто-то предложил более быстрый алгоритм. Пробовал делать через 'sqrt(number)' вместо 'number//2' и одновременным добавлением 'x, number//x', но что-то не срослось...

@dondublon · 15.05.2015, 10:30

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import numpy as np
 
n = 10000
div_sum = np.zeros(n, dtype=np.int)
 
for i in xrange(n):
    r = np.arange(1, i/2+1)
    div_sum[i] = np.sum(r[np.remainder(i, r)==0])
                                 
print div_sum[220], div_sum[284]
 
rn = np.arange(n)
div_sum1 = div_sum.copy()
div_sum1[div_sum1 >= n] = 0
friendly = rn[np.logical_and(rn[div_sum1][div_sum1] == rn, rn[div_sum1] != rn)]
print friendly

В принципе, можно сделать и без цикла, на чистом numpy, но там сложно получается, я запутался

В предпоследней строчке, rn[div_sum1] != rn - отфильтровываем "совершенные" числа, потому что они тоже туда попадают.

Добавлено через 29 минут
Да, результат, для проверки

Последнюю строчку меняем на:

Python
1
print zip(friendly, div_sum[friendly])

Вывод

Code
1
[(220, 284), (284, 220), (1184, 1210), (1210, 1184), (2620, 2924), (2924, 2620), (5020, 5564), (5564, 5020), (6232, 6368), (6368, 6232)]

Добавлено через 21 минуту
Другой вариант получения div_sum, без цыкла.

Python
1
2
3
4
5
6
7
8
# second variant
r1 = np.arange(1, n)
d_arr, n_arr = np.meshgrid(r1, r1)
rem = np.remainder(n_arr, d_arr)
 
d0 = np.where(rem==0, d_arr, np.zeros((n-1, n-1)))
div_sum0 = np.sum(d0, axis=1, dtype=int) - r1
div_sum = np.insert(div_sum0, 0, 0)

Добавлено через 19 минут
И ещё один вариант, без meshgrid, но через newaxis:

Python
1
2
3
4
5
6
7
8
9
10
11
12
# second variant
r1 = np.arange(1, n)
#d_arr, n_arr = np.meshgrid(r1, r1)
#rem = np.remainder(n_arr, d_arr)
rem = np.zeros((n-1, n-1))
rem[:, :] = np.remainder(r1[:, np.newaxis], r1[ np.newaxis, :])
 
#d0 = np.where(rem==0, d_arr, np.zeros((n-1, n-1)))
d0 = np.zeros((n-1, n-1))
d0[:, :] = np.where(rem==0, r1[ np.newaxis, :], 0)
div_sum0 = np.sum(d0, axis=1, dtype=int) - r1
div_sum = np.insert(div_sum0, 0, 0)

(Да, я numpy-виртуоз!)

@TroSer · 15.05.2015, 14:35

Не по теме:

Сообщение от dondublon

(Да, я numpy-виртуоз!)

:).

Добавлено через 3 часа 48 минут
Получилось ускорить работу программы:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from math import sqrt
    
limit = 10000
pairs = {}
     
def divisors_sum(number):
    lst = []
    for x in range(1, int(sqrt(number))+1):
        if number%x == 0:
            if (number or x) != number//x:
                lst.append(x)
                lst.append(number//x)
            else:
                lst.append(1)
    return sum(lst)
    
for i in range(1, limit+1):
    aggr = divisors_sum(i)
    if i == divisors_sum(aggr) and i != aggr :
        if i not in pairs:
            pairs[i] = aggr

@dondublon · 15.05.2015, 14:56

TroSer, простейшая модицификация твоего варианта - кэшируем divisors_sum. Сейчас вызывается дважды для большинства чисел.

Python
1
2
3
4
5
6
7
8
9
ds = [0] * (limit + 1)
for i in range(1, limit+1):
    ds[i] = divisors_sum(i)
    
for i in range(1, limit+1):
    aggr = ds[i]# divisors_sum(i)
    if aggr <= limit and i == ds[aggr] and i != aggr :
        if i not in pairs:
            pairs[i] = aggr

Твой начальный вариант считает 1.8 сек, этот - 1.0. Мой первый вариант считает 0.58

зато второй - 3.9

Долго шебуршится по двумерным массивам.

@vasya58 · 18.05.2015, 06:54

Комментарий модератора

Один вопрос - одна тема!

@Magprone · 01.01.2021, 01:10

Я не понимаю зачем настолько замороченные коды? Вот мой прекрасно понятный и быстродейственный код. Или он что то забывает?

Python
1
2
3
4
5
6
for num1 in range(1, 10001):
    num1_del = [num for num in range(1, num1) if num1 % num == 0]
    num2 = sum(num1_del)
    num2_del = [num for num in range(1, num2) if num2 % num == 0]
    if num1 == sum(num2_del) and num2 == sum(num1_del):
        print(f'{num1} and {num2} is friend!')

@Catstail · 01.01.2021, 10:01

Чтобы снизить к-во операций деления, нужно "двигаться до квадратного корня" и сразу же получать парный делитель:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import time
 
t_start=time.time()
result=[]
for num in range(2,10001):
    sd_num=1 
    i=2 
    while(i*i<=num):
        (p,q)=divmod(num,i)
        if q==0:
            sd_num+=i
            if p!=i:
                sd_num+=p
        i=i+1        
    mun=sd_num
    sd_mun=1
    i=2 
    while(i*i<=mun):
        (p,q)=divmod(mun,i)
        if q==0:
            sd_mun+=i
            if p!=i:
                sd_mun+=p
        i=i+1  
    if num==sd_mun and mun==sd_num:
        if (num != mun) and (num < mun):
            result.append((num,mun))
print(result)
    
t_fin=time.time()
print(t_fin-t_start)

@SasaSupov · 19.02.2021, 08:05

Вот это тупо за ~0,09
но всё равно медленно.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from time import time
 
 
def sumdiv(n):
    d = 2
    s = 1
    while d * d < n:
        if n % d == 0:
            s += d
            s += n // d
        d += 1
    return s + d if d * d == n else s
 
 
k = int(input())
st = time()
for i in range(2, k + 1):
    b = sumdiv(i)
    if k >= b > i == sumdiv(b):
        print(i, b)
 
print(time() - st)

@pustelekno · 17.04.2022, 14:36

Скорее всего ускорение этой задачи как-то связано с задачей нахождения НОД и алгоритмом Евклида. Но пока я не понимаю как.

Наибольший общий делитель двух натуральных чисел (НОД)
НОД для a и b:

https://www.silvertests.ru/Use... /9/NOD.jpg

Его реализация

Code
1
2
3
4
5
6
7
8
9
def NOD(a,b):
  while a!=0 and b!=0:
    if a>b:
      a=a%b
    else:
      b=b%a
  return a+b
a, b = map(int, input().split())
print(NOD(a,b))

Но как это связано с этой задачей, может кто-то из еще додумается.

Почему такая уверенность? На сильвертесте все последовательно. Сначала идет эта задача с Евклидом, а потом про дружественные числа. И... при n//2+1 мне не хватает скорости решить все примеры, думаю надо как-то прикручивать Евклида... Всякие библиотеки там исключаются пока.

@pustelekno · 17.04.2022, 21:18

Code
1
2
3
s=1
for i in range (2,int(N**0.5+1)):
    if not(N%i): s+=i+N//i

Так получилось уложиться по времени.
И еще кое-что - not(N%i) значительно быстрее, чем N%i==0

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

@opdfpg 1 / 1 / 0 Регистрация: 13.05.2015 Сообщений: 9

	Дружественные числа до 10000 13.05.2015, 14:54. Показов 24405. Ответов 10 Метки нет (Все метки) Здравствуйте. Помогите с задачкой: Найти все пары дружественных чисел до 10 000. Пара дружественных чисел - это два различных натуральных числа, для которых сумма всех делителей первого числа равна второму числу и наоборот, сумма всех делителей второго числа равна первому числу. Например, 220 и 284 (делители для 220 это 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 и 110, сумма делителей равна 284. Делители для 284 это 1, 2, 4, 71 и 142, сумма которых равна 220). 1