Аватар для Not_
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64

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

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

Author24 — интернет-сервис помощи студентам
Добрый вечер.
Есть задача: зная простые делители числа и их количество, найти все делители числа.
У меня есть словарь, в котором хранятся простые делители и их количество. Для числа 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
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
19.04.2018, 20:52
Ответы с готовыми решениями:

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

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

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

23
 Аватар для FilArt97
37 / 36 / 16
Регистрация: 11.03.2018
Сообщений: 95
19.04.2018, 21:05
Ваша догадка сработает однозначно
1
 Аватар для Not_
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
19.04.2018, 21:06  [ТС]
FilArt97, к сожалению, я не знаю, как её реализовать. Вы не могли бы немного намекнуть на реализацию?
0
 Аватар для FilArt97
37 / 36 / 16
Регистрация: 11.03.2018
Сообщений: 95
19.04.2018, 21:11
Решение в лоб вас устроит?
0
 Аватар для Not_
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
19.04.2018, 21:14  [ТС]
FilArt97, да, если можно.
0
956 / 712 / 275
Регистрация: 10.12.2016
Сообщений: 1,754
19.04.2018, 21:37
Лучший ответ Сообщение было отмечено 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
 Аватар для Not_
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
19.04.2018, 21:41  [ТС]
vic5710, спасибо большое!
0
956 / 712 / 275
Регистрация: 10.12.2016
Сообщений: 1,754
19.04.2018, 21:42
хотя зачем здесь словарь - не знаю
Python
1
2
3
>>> x = 20
>>> [i for i in range(2,x+1) if not x%i]
[2, 4, 5, 10, 20]
1
 Аватар для Not_
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
19.04.2018, 21:44  [ТС]
vic5710, очень благодарна.
0
 Аватар для FilArt97
37 / 36 / 16
Регистрация: 11.03.2018
Сообщений: 95
19.04.2018, 22:09
Лучший ответ Сообщение было отмечено 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
 Аватар для Not_
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
19.04.2018, 22:11  [ТС]
FilArt97, очень Вам признательна за код, буду разбираться.
0
 Аватар для FilArt97
37 / 36 / 16
Регистрация: 11.03.2018
Сообщений: 95
19.04.2018, 22:37
Лучше используйте первый код, который вам уже предложили, там получше

Добавлено через 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
Фрилансер
 Аватар для Black Fregat
3709 / 2082 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
21.04.2018, 17:17
Лучший ответ Сообщение было отмечено 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
 Аватар для Not_
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
21.04.2018, 18:07  [ТС]
Black Fregat, большое спасибо!

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

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

Добавлено через 29 секунд
Диапазон от 1 до 2 в 30 степени.
0
Фрилансер
 Аватар для Black Fregat
3709 / 2082 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
21.04.2018, 23:39
Так это же совсем другое дело!
Не надо генерировать список делителей, надо сразу считать сумму
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
 Аватар для Not_
5 / 5 / 10
Регистрация: 13.06.2017
Сообщений: 64
21.04.2018, 23:46  [ТС]
Black Fregat, у Вас s - это сумма делителей?
0
Фрилансер
 Аватар для Black Fregat
3709 / 2082 / 567
Регистрация: 31.05.2009
Сообщений: 6,683
21.04.2018, 23:47
А можно сделать грязный хак - явно забить все соверщенные числа в диапазоне, их совсем немного

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

Добавлено через 1 минуту
Да, так можно сделать, но хотелось бы решить без таких хаков)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
21.04.2018, 23:50
Помогаю со студенческими работами здесь

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

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

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

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

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


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

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

Новые блоги и статьи
MVC фреймворк в PHP
Jason-Webb 19.04.2025
Архитектурный паттерн Model-View-Controller (MVC) – это не просто модный термин из мира веб-разработки. Для PHP-программистов это фундаментальный подход к организации кода, который радикально меняет. . .
Dictionary Comprehensions в Python
py-thonny 19.04.2025
Python славится своей выразительностью и лаконичностью, что позволяет писать чистый и понятный код. Среди множества синтаксических конструкций языка особое место занимают словарные включения. . .
Шаблоны и протоколы для создания устойчивых микросервисов
ArchitectMsa 19.04.2025
Микросервисы — архитектурный подход, разбивающий сложные приложения на небольшие, независимые компоненты. Вместо монолитного гиганта, система превращается в созвездие небольших взаимодействующих. . .
Изменяемые и неизменяемые типы в Python
py-thonny 19.04.2025
Python славится своей гибкостью и интуитивной понятностью, а одна из главных его особенностей — это система типов данных. В этом языке все, включая числа, строки, функции и даже классы, является. . .
Интеграция Hangfire с RabbitMQ в проектах C#.NET
stackOverflow 18.04.2025
Разработка современных . NET-приложений часто требует выполнения задач "за кулисами". Это может быть отправка email-уведомлений, генерация отчётов, обработка загруженных файлов или синхронизация. . .
Построение эффективных запросов в микросервисной архитектуре: Стратегии и практики
ArchitectMsa 18.04.2025
Микросервисная архитектура принесла с собой много преимуществ — возможность независимого масштабирования сервисов, технологическую гибкость и четкое разграничение ответственности. Но как часто бывает. . .
Префабы в Unity: Использование, хранение, управление
GameUnited 18.04.2025
Префабы — один из краеугольных элементов разработки игр в Unity, представляющий собой шаблоны объектов, которые можно многократно использовать в различных сценах. Они позволяют создавать составные. . .
RabbitMQ как шина данных в интеграционных решениях на C# (с MassTransit)
stackOverflow 18.04.2025
Современный бизнес опирается на множество специализированных программных систем, каждая из которых заточена под решение конкретных задач. CRM управляет отношениями с клиентами, ERP контролирует. . .
Типы в TypeScript
run.dev 18.04.2025
TypeScript представляет собой мощное расширение JavaScript, которое добавляет статическую типизацию в этот динамический язык. В JavaScript, где переменная может свободно менять тип в процессе. . .
Погружение в Kafka: Концепции и примеры на C# с ASP.NET Core
stackOverflow 18.04.2025
Apache Kafka изменила подход к обработке данных в распределенных системах. Эта платформа потоковой передачи данных выходит далеко за рамки обычной шины сообщений, предлагая мощные возможности,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru