5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
1

Зная простые делители числа и их количество, найти все делители числа

19.04.2018, 20:52. Показов 6373. Ответов 23
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Добрый вечер.
Есть задача: зная простые делители числа и их количество, найти все делители числа.
У меня есть словарь, в котором хранятся простые делители и их количество. Для числа 20, например: {2: 2, 5: 1}. Имея этот словарь, нужно получить список с делителями; т.е. для числа 20: [2, 4, 5, 10, 20].
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
n = int(input())
n1 = n
s = {}
for i in range(2, int(n1 ** 0.5) + 1):
    while n % i == 0:
        if i not in s:
            s[i] = 1
        else:
            s[i] += 1
        n //= i
    if n == 1:
        break
print(s)
Подскажите пожалуйста, как это можно сделать?


P.S. Была у меня одна догадка, но что-то я в ней сомневаюсь. Получается, нужно брать комбинации всех ключей словаря?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.04.2018, 20:52
Ответы с готовыми решениями:

Все простые делители числа
Здравствуйте, написал код для нахождения всех простых делителей числа, но он долго работает (я...

Получить все простые делители числа
Дано натуральное число n. Получить все простые делители этого числа Перевести на Python CLS...

Получить все делители числа q, взаимно простые с p
Даны целые числа p и q. Получить все делители числа q, взаимно простые с p.

Получить все делители числа q взаимно простые с p
Даны натуральные числа p и q. Получить все делители числа q взаимно просты с p.

23
37 / 36 / 16
Регистрация: 11.03.2018
Сообщений: 95
19.04.2018, 21:05 2
Ваша догадка сработает однозначно
1
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
19.04.2018, 21:06  [ТС] 3
FilArt97, к сожалению, я не знаю, как её реализовать. Вы не могли бы немного намекнуть на реализацию?
0
37 / 36 / 16
Регистрация: 11.03.2018
Сообщений: 95
19.04.2018, 21:11 4
Решение в лоб вас устроит?
0
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
19.04.2018, 21:14  [ТС] 5
FilArt97, да, если можно.
0
881 / 659 / 253
Регистрация: 10.12.2016
Сообщений: 1,610
19.04.2018, 21:37 6
Лучший ответ Сообщение было отмечено Not_ как решение

Решение

например через itertools
Python
1
2
3
4
5
6
7
8
9
10
11
>>> from itertools import accumulate
>>> def f(lst):
    out = []
    while True:
        if not lst: return set(out)
        out += list(accumulate(lst,lambda a,b: a*b))
        lst = lst[1:]
 
        
>>> f([2,2,5])
{2, 4, 5, 10, 20}
1
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
19.04.2018, 21:41  [ТС] 7
vic5710, спасибо большое!
0
881 / 659 / 253
Регистрация: 10.12.2016
Сообщений: 1,610
19.04.2018, 21:42 8
хотя зачем здесь словарь - не знаю
Python
1
2
3
>>> x = 20
>>> [i for i in range(2,x+1) if not x%i]
[2, 4, 5, 10, 20]
1
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
19.04.2018, 21:44  [ТС] 9
vic5710, очень благодарна.
0
37 / 36 / 16
Регистрация: 11.03.2018
Сообщений: 95
19.04.2018, 22:09 10
Лучший ответ Сообщение было отмечено Not_ как решение

Решение

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
from itertools import permutations
from functools import reduce
 
num = 20
subs = {2: 2, 5: 1}
 
 
def main(num, subs):
    just_subs = []
    for sub in subs:
        repeats = subs[sub]
        for repeat in range(repeats):
            just_subs.append(sub)
 
    all_variants =[list(i) for i in permutations(just_subs)]
    res = set()
    while all_variants[0]:
        for var in all_variants:
            res.add(reduce((lambda a, x: a * x), var))
            var.pop()
    return res
 
 
print(main(num, subs))
Добавлено через 1 минуту
Да уж, что-то я слегка не тем путем пошел

Добавлено через 38 секунд
Хотя стоп, я просто привязался к словарю, поэтому конечно да
1
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
19.04.2018, 22:11  [ТС] 11
FilArt97, очень Вам признательна за код, буду разбираться.
0
37 / 36 / 16
Регистрация: 11.03.2018
Сообщений: 95
19.04.2018, 22:37 12
Лучше используйте первый код, который вам уже предложили, там получше

Добавлено через 25 минут
Цитата Сообщение от vic5710 Посмотреть сообщение
>>> from itertools import accumulate
>>> def f(lst):
out = []
while True:
if not lst: return set(out)
out += list(accumulate(lst,lambda a,b: a*b))
lst = lst[1:]
>>> f([2,2,5])
{2, 4, 5, 10, 20}
Для 30-ти не работат:

Python
1
2
print(f([2, 3, 5]))  # [2, 3, 5, 6, 15, 30]
Вместо [2, 3, 5, 6, 10, 15, 30]
0
Фрилансер
3704 / 2076 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
21.04.2018, 17:17 13
Лучший ответ Сообщение было отмечено Not_ как решение

Решение

Python
1
2
3
4
5
d = {2: 3, 3: 2, 5: 1}
res = [1]
for p, k in d.items():
  res = [a*p**i for a in res for i in range(k+1)]
print(sorted(res))
1
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
21.04.2018, 18:07  [ТС] 14
Black Fregat, большое спасибо!

Добавлено через 3 минуты
Протестировала все способы, все коды - все предложенные решения выдают Time Limit, ограничение по времени - 0.1 секунда. Как можно их усовершенствовать?

P.S. Если что, то нахождение простых делителей у меня уложилось в 0.1 секунды.
0
Фрилансер
3704 / 2076 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
21.04.2018, 21:12 15
А можно более точную формулировку задачи? Особенно диапазон чисел
0
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
21.04.2018, 21:21  [ТС] 16
Black Fregat, напишите программу, которая говорит, является ли данное число совершенным. Попробуйте генерировать делители числа из его разложения на простые множители.

Добавлено через 29 секунд
Диапазон от 1 до 2 в 30 степени.
0
Фрилансер
3704 / 2076 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
21.04.2018, 23:39 17
Так это же совсем другое дело!
Не надо генерировать список делителей, надо сразу считать сумму
Python
1
2
3
4
d = {2: 3, 3: 2, 5: 1}
s = 1
for p, k in d.items():
  s *= (p**(k+1) - 1) // (p - 1)
1
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
21.04.2018, 23:46  [ТС] 18
Black Fregat, у Вас s - это сумма делителей?
0
Фрилансер
3704 / 2076 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
21.04.2018, 23:47 19
А можно сделать грязный хак - явно забить все соверщенные числа в диапазоне, их совсем немного

Добавлено через 1 минуту
Цитата Сообщение от Not_ Посмотреть сообщение
s - это сумма делителей
Да, только всех делителей. Для суммы собственных делителей нужно вычесть само число.
0
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
21.04.2018, 23:50  [ТС] 20
Black Fregat, но разве сумма делителей числа 360 равна 1170?

Добавлено через 1 минуту
Да, так можно сделать, но хотелось бы решить без таких хаков)
0
21.04.2018, 23:50
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
21.04.2018, 23:50
Помогаю со студенческими работами здесь

Как найти простые делители для числа?
Всем привет. Подскажите как для числа найти простые делители?

Четные делители, нечетные делители, простые делители, составные делители, все делители
Помогите с задачей, не как не получается сделать. Создать HTML-документ p53.html, реализующий...

Файлы. Найти наименьший и наибольший общие делители, также определить все простые числа и их количество
создать файл из натуральных чисел. в файле натуральных чисел найти наименьший и наибольший общие...

Найти и напечатать все простые делители заданного натурального числа числа
1)найти и напечатать все простые делители заданного натурального числа числа

Найти все простые делители числа
Есть такая задача Задано натуральное число M. Найти все его простые делители

Найти все простые делители числа
Опишите функцию простые_делители(m), которая находит и выводит все простые делители числа m ...

Найти все простые делители числа
Программа должна находить все простые делители числа. Выводит не все делители и некоторые не...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru