Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/64: Рейтинг темы: голосов - 64, средняя оценка - 4.75
1 / 1 / 0
Регистрация: 13.05.2015
Сообщений: 9
1

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

13.05.2015, 14:54. Показов 13298. Ответов 8
Метки нет (Все метки)

Здравствуйте. Помогите с задачкой: Найти все пары дружественных чисел до 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

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.05.2015, 14:54
Ответы с готовыми решениями:

Дружественные числа
Программа должна вывести слово 'YES', если полученные числа – дружественные, и слово 'NO' в...

Найти дружественные числа, принадлежащие отрезку [1; 10000]
Помогите, сегодня сдавать надо. Дружественными числами являются два натуральных числа, таких,...

Дан массив символьных строк. Найти количество двухзачных чисел. Числа в строках лежат в пределах от -10000 до 10000
Задача: Дан массив символьных строк. Найти количество двухзачных чисел. Числа в строках лежат в...

Даны целые числа m и n (n,m < 10000) и действительные числа a1, a2,.......an найти целое число i (1<=i<=n-m) для которого сумма ai+ai+1+.....+ai+m
помогите пожалуйста решить

8
23 / 23 / 16
Регистрация: 17.01.2014
Сообщений: 81
13.05.2015, 18:14 2
Цитата Сообщение от 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', но что-то не срослось...
0
Эксперт Python
4531 / 1959 / 351
Регистрация: 17.03.2012
Сообщений: 9,862
Записей в блоге: 5
15.05.2015, 10:30 3
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])
Вывод
Код
[(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-виртуоз!)
0
23 / 23 / 16
Регистрация: 17.01.2014
Сообщений: 81
15.05.2015, 14:35 4

Не по теме:

Цитата Сообщение от 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
0
Эксперт Python
4531 / 1959 / 351
Регистрация: 17.03.2012
Сообщений: 9,862
Записей в блоге: 5
15.05.2015, 14:56 5
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
Долго шебуршится по двумерным массивам.
1
vasya58
18.05.2015, 06:54
  #6
 Комментарий модератора 
Один вопрос - одна тема!
0
0 / 0 / 0
Регистрация: 31.12.2020
Сообщений: 8
01.01.2021, 01:10 7
Я не понимаю зачем настолько замороченные коды? Вот мой прекрасно понятный и быстродейственный код. Или он что то забывает?
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!')
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
29579 / 16145 / 3224
Регистрация: 12.02.2012
Сообщений: 26,694
Записей в блоге: 5
01.01.2021, 10:01 8
Чтобы снизить к-во операций деления, нужно "двигаться до квадратного корня" и сразу же получать парный делитель:

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)
1
0 / 0 / 0
Регистрация: 21.10.2015
Сообщений: 5
19.02.2021, 08:05 9
Вот это тупо за ~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)
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.02.2021, 08:05

Для заданного числа Н(1<Н<10000) написать программу, которая находит все совершенные числа, меньшие Н
Число называется совершенным,если сумма его делителей (кроме него самого) равна этому числи....

Массивы... Дружественные числа, счасливые числа... и т.д.
Всем привет... Я тут впервый раз... Дело обстоит так... Я уже ни знаю что и делать... Перепробовал...

Дружественные числа
Дружественные числа Даны два целых положительных числа M, N. Требуется найти все «дружественные»...

Дружественные числа
Подскажите, программа не работает var a,b,i,s,r,j:integer; begin write('Введите первое...

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

Дружественные числа
Даны два натуральных числа. Проверить, являются ли они дружественными. Для подсчета суммы...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.