Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.69/29: Рейтинг темы: голосов - 29, средняя оценка - 4.69
4219 / 1930 / 901
Регистрация: 27.03.2020
Сообщений: 3,747
1

Разложение на множители

19.08.2020, 09:43. Показов 5600. Ответов 31
Метки нет (Все метки)

Задача разложения числа на простые(!) множители решается многими методами и довольно быстро.
Существует ли встроенная функция или метод для волучения всех(!) вариантов получения числа произведением других натуральных чисел.
Для себя сделал, но, например, для числа 720 время нахождения всех вариантов занимает ~ 0,3 сек
Хотелось бы быстрее
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.08.2020, 09:43
Ответы с готовыми решениями:

Разложение на множители
Добрый день. Нужно разложить число на множители в виде: 24=2*2*2*2*3. Но в программе получается...

Разложение на простые множители
Разложение на простые множители Требуется разложить целое число N на простые множители с учётом их...

Разложение на простые множители
Требуется разложить целое число N на простые множители и вывести результат в порядке возрастания...

Разложение на множители
Требуется разложить многочлен на неприводимые множители f(x)=x^4+2x^3-x^2+2x-2 Как записать в...

31
Эксперт Python
4460 / 1894 / 343
Регистрация: 17.03.2012
Сообщений: 9,714
Записей в блоге: 5
19.08.2020, 11:13 2
Что ускорять будем?
0
4219 / 1930 / 901
Регистрация: 27.03.2020
Сообщений: 3,747
19.08.2020, 12:32  [ТС] 3
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
def delit(a) :
    res = []
    i = 1
    while i * i < a + 1 :
        if a % i == 0 :
            temp = [i, a // i]
            res.append(temp)
        i += 1
    return res 
    
n = int(input())
npr = [2,3,5,7,11,13,17,19,23,29]
 
# первичное разложение на парные делители
fact = delit(n)
 
flen = len(fact)
while True :
    for j in range(flen) :
        zero = 1
 
        # если в очередном списке делителей 
        #есть "1", пропустить
        if 1 not in fact[j] :
            zero = 0
            n1 = list(fact[j])
 
            # "вытаскиваем" последний делитель из списка
            # и ищем все попарные разложения на множители
            factj = delit(n1.pop())
 
            # каждую полученную пару 
            #объединяем со списком
            for k in range(len(factj)) :
                factj[k].extend(n1)
                factj[k].sort()
                fact.append(factj[k])
    flen = len(fact)
 
    # если zero не изменилось во всех списках,
    # все варианты найдены
    if zero == 1:
        break
 
# удаляем 1 из всех вариантов
for ik in fact :
    ik.sort(reverse=True)
    if ik[-1] == 1 :
        ik.pop()
 
# удаляем одинаковые списки
j =[0]
resj = []
for i in fact :
    if i != j :
        resj.append(i)
    j=i
 
######################################
Добавлено через 3 минуты
Основные "прожорливые" - 34-36 строки

Добавлено через 14 минут
Нашел одну "ошибку": после 51-й строчки нужно
Python
1
fact.sort()
0
Эксперт Python
4460 / 1894 / 343
Регистрация: 17.03.2012
Сообщений: 9,714
Записей в блоге: 5
19.08.2020, 12:42 4
Чота я вообще не понял, что у вас в большом цикле while.
Но по функции delit могу посоветовать - а зачем там перебираются все потенциальные делители, через +1? Перебирайте только простые. Простые должны быть закешированы.

Добавлено через 6 минут
Псевдокод, как это должно быть:

Код
список_простых_чисел. в нём курсор = 0.
список_делителей = []
остаток := число. 

пока остаток > 1:
    получить простой_делитель.
        пока остаток делится на простой_делитель:
            остаток := остаток // простой_делитель
            список_делителей.append(простой_делитель)
Как-то так. У вас что-то сложное.
0
Status 418
1706 / 890 / 317
Регистрация: 26.11.2017
Сообщений: 2,461
19.08.2020, 12:48 5
Какая задача?
0
4219 / 1930 / 901
Регистрация: 27.03.2020
Сообщений: 3,747
19.08.2020, 12:52  [ТС] 6
Вся задача звучит так:
Для заданного числа N найти наименьшее число, имеющего ровно N делителей

Добавлено через 28 секунд
Выложенный код - часть решения

Добавлено через 1 минуту
Само решение основано на:
Количество делителей числа равно произведению степеней плюс 1 всех его простых множителей

Добавлено через 1 минуту
Число 24
Состоит из 2^3 * 3^1
Значит 24 имеет = (3+1)*(1+1) = 8 множителей
0
Эксперт Python
4460 / 1894 / 343
Регистрация: 17.03.2012
Сообщений: 9,714
Записей в блоге: 5
19.08.2020, 12:56 7
Gdez, простых или любых?
В любом случае, разложением на простые делители тут как-то не очень пахнет.

Добавлено через 2 минуты
Цитата Сообщение от Gdez Посмотреть сообщение
Значит 24 имеет = (3+1)*(1+1) = 8 множителей
Откуда тут +1?
24=2*2*2*3. Откуда тут 8?

Добавлено через 48 секунд
Цитата Сообщение от Gdez Посмотреть сообщение
Вся задача звучит так:
Для заданного числа N найти наименьшее число, имеющего ровно N делителей
Если речь о простых множителях, то наименьшее будет 2^N. Ничего раскладывать не надо.
0
4219 / 1930 / 901
Регистрация: 27.03.2020
Сообщений: 3,747
19.08.2020, 12:59  [ТС] 8
В задаче N < 1000
Значит количество простых множителей <= 10
Отсюда в коде есть
Python
1
npr = [2,3,5,7,11,13,17,19,23,29]
Полученные списки "resj", перебирая, возвожу соответствующие элементы списка "npr" и перемножаю их
Ответ - искомое число

Добавлено через 1 минуту
Нет.
4 делителя у 6 - это 1,2,3,6
А 2^4 = 16 > 6
В понятие делитель входят все числа от 1 до самого числа
0
Эксперт Python
4460 / 1894 / 343
Регистрация: 17.03.2012
Сообщений: 9,714
Записей в блоге: 5
19.08.2020, 12:59 9
Gdez, если простых множителей, то 2^N. Если различных простых множителей, то [p1*...*pN], где p1...pN - простые числа по порядку, нанчиная с 2. В любом случае, раскладывать не надо.
0
4219 / 1930 / 901
Регистрация: 27.03.2020
Сообщений: 3,747
19.08.2020, 13:01  [ТС] 10
У 24 делители 1,2,3,4,6,8,12,24
0
Эксперт Python
4460 / 1894 / 343
Регистрация: 17.03.2012
Сообщений: 9,714
Записей в блоге: 5
19.08.2020, 13:01 11
Gdez, а, то есть всех делителей, включая составные, не повторяющиеся, включая 1 и само число.
Для 24 это 1, 2, 3, 4, 6, 12, 24. То есть 7. Я ничего не напутал?
0
4219 / 1930 / 901
Регистрация: 27.03.2020
Сообщений: 3,747
19.08.2020, 13:02  [ТС] 12
Еще 8-ка
0
Эксперт Python
4460 / 1894 / 343
Регистрация: 17.03.2012
Сообщений: 9,714
Записей в блоге: 5
19.08.2020, 13:02 13
А, забыл 8. Понятно.
0
4219 / 1930 / 901
Регистрация: 27.03.2020
Сообщений: 3,747
19.08.2020, 13:04  [ТС] 14
Былы идея - N разложить на простые множители и найти все варианты перемножения, при которых резултатом будет N
С помощью itertools. Но запутался)))
0
Эксперт Python
4460 / 1894 / 343
Регистрация: 17.03.2012
Сообщений: 9,714
Записей в блоге: 5
19.08.2020, 13:05 15
Уже не так очевидно, но, пмм, тут надо идти конструктивным путём, то есть составить число. Перебор сдохнет.
0
4219 / 1930 / 901
Регистрация: 27.03.2020
Сообщений: 3,747
19.08.2020, 13:10  [ТС] 16
В "идеальном" решении время 60 мсек
У меня 372

Добавлено через 3 минуты
Перебором уже на N=16 больше 2 сек
0
Модератор
Эксперт по электронике
7523 / 3712 / 1455
Регистрация: 01.02.2015
Сообщений: 11,550
Записей в блоге: 2
19.08.2020, 13:23 17
Может быть так?..
Оценить возможную длину массива A[] - например последующим экспериментальным прогоном в цикле от 0 до 1000.

Элемент массива A[i] - это количество делителей числа i.
Потом во вложенных циклах заполнил бы массив A[]
Код
for i in range(1,N)
    for j in range(0,N)
        A[i*j] += 1   - тут можно иначе организовать цикл, чтобы было сложение, вместо умножения
        if A[i*j]==N: printf(i*j)
Понятно, что N делителей будет у числа, превосходящего N в несколько раз.
0
Эксперт Python
4460 / 1894 / 343
Регистрация: 17.03.2012
Сообщений: 9,714
Записей в блоге: 5
19.08.2020, 13:30 18
Составляем примерно так.
Для N=2, решение 2, список [1,2].
К этому списку можно добавить следующее наименьшее число, 3. Но тогда к нему автоматически добавится и 6. И получим решение для N=4. Таким образом заполним некоторые числа для массива ответов.
Для незаполненых (3) будем искать как лучшее из предыдущиих с добавлением чего-то. И тоже будем "попадать" не в те клетки. Но постепенно все заполним.
То есть, для ответа для N=3 у нас есть знание про [1,2] для N=2. По очереди добаволяем к списку : 3 - уже было, 4 - о, подходит. И так далее.

Добавлено через 2 минуты
Разложение на простые множители тут и правда может выскочить, для проверки после очередного добавления.
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from functools import reduce
from operator import mul
npr = [2,3,5,7,11,13,17,19,23,29]
 
 
def prime_factors(n):
    primes_iter = iter(npr)
    remainder = n
    result = []
 
    while remainder > 1:
        factor = next(primes_iter)
        while remainder % factor == 0:
            result.append(factor)
            remainder //= factor
 
    # lets check:
    assert reduce(mul, result) == n
    return result
 
 
print(prime_factors(720))
0
4219 / 1930 / 901
Регистрация: 27.03.2020
Сообщений: 3,747
19.08.2020, 14:07  [ТС] 19
N = 720
Ответ = 61261200
61261200 = 2^4 * 3^2 * 5^2 * 7^1 * 11^1 * 13^1 * 17^1
Проверка - (4+1)*(2+1)*(2+1)*(1+1)*(1+1)*(1+1)*(1+1)
5 * 3 * 3 * 2 * 2 * 2 * 2 = 720

Добавлено через 7 минут
Например для N = 32 наилучшим будет = 4*2*2*2
Степени - 3, 1, 1, 1
2^3*3*5*7 = 840
Здесь "4" - непростой множитель

Добавлено через 3 минуты
ФедосеевПавел,
Вылетает по времени
Ну и множителей может быть от одного до десяти
Цикл по двум, трем, четырем ..... ?
Долго

Добавлено через 3 минуты
Есть идругие, например, 24
Для него -4*3*2
И решение - 360
0
Модератор
Эксперт по электронике
7523 / 3712 / 1455
Регистрация: 01.02.2015
Сообщений: 11,550
Записей в блоге: 2
19.08.2020, 15:47 20
Т.е. нужно решить уравнение

Пусть наше искомое число X раскладывается на простые множители
https://www.cyberforum.ru/cgi-bin/latex.cgi?X=2^{b_0}\cdot 3^{b_1}\cdot 5^{b_2}...
Согласно формуле из
https://ru.wikihow.com/найти-к... лого-числа
число X имеет ровно N делителей, причём
https://www.cyberforum.ru/cgi-bin/latex.cgi?N=(b_0+1)\cdot (b_1+1)\cdot (b_2+1)\cdot ...

И теперь встаёт задача разложить N на множители (в количестве от 1 до максимума), чтобы X было минимально.

Похоже, что нужно максимально длинное разложение N.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.08.2020, 15:47

Заказываю контрольные, курсовые, дипломные работы и диссертации здесь.

Разложение на множители
Здравствуйте, подскажите, пожалуйста, по какой логике в данном случае нужно действовать, чтобы...

Разложение на множители
Нужно разложить число на простые множители в C++ Builder!!!Помогите кто чем могет!! Добавлено...

Разложение на множители
как можно разложить на множители выражение x^3-9x^2+20x-3 ?

Разложение на множители
Дано натуральное число N. Разложить его на простые множители. Алгоритм решения задачи: ...

Разложение на множители
добрый день! являюсь студентом 1-го курса, по инфе проходим visual basic. раньше задавали простые...

Разложение на множители
Дано натуральное число n&gt;1. Выведите все простые множители этого числа в порядке неубывания с...


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

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

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