Разложить число на простые множители

#python

Как в питоне разложить число на множители, чтобы их произведение было равно этому
числу.  

number=int(input("Integer: "))
for i in range(1, number+1):
    if(number%i==0):
        print(i)


При вводе числа (например) 63. На выходе получается:

1
3
7
9
21
63




#!/usr/bin/env python3
n=int(input("Integer: ")) 
factors = []
d = 2
while d * d <= n:
        if n % d == 0:
            factors.append(d)
            n//=d
        else:
            d += 1
        if n > 1:
            factors.append(n)
        else:
            break
print('{} = {}' .format(n,factors))


На выходе получется: 7 = [63, 3, 21, 3, 7]



А мне необходимо получить:
63 = 3 * 3 * 7
    

Ответы

Ответ 1

Эта задача называется Факторизация целых чисел

Одна из реализаций(взято с OEIS#A238724):

def primfacs(n):
   i = 2
   primfac = []
   while i * i <= n:
       while n % i == 0:
           primfac.append(i)
           n = n / i
       i = i + 1
   if n > 1:
       primfac.append(n)
   return primfac


Ответ 2

В коде есть два существенных момента, из-за которых он ищет все делители вместо факторизации.
Добавлю ещё одно изменение ради оптимизации и получится такой код:

http://ideone.com/qi60fH

import math

number=int(input())

for i in range(2, int(math.sqrt(number)) + 1): # обычно делитель не будет больше корня
    while (number % i == 0): # while, а не if
        print(i)
        number //= i # убираем множитель из числа

if (number != 1): # но один делитель может быть больше корня
    print (number)


PS: Но вообще вариант с циклом из соседнего ответа лучше.


Ответ 3

Посмотрите, например, как сделано здесь. Существуют более сложные и эффективные методы.
А также обратите внимание на решето Эратосфена (тут). Если вы хотите получать факторизацию
не для одного числа, а для большого набора числел, то выгоднее использовать перебор
по простым. Об этом я расскажу чуть ниже.

Кроме того, я думаю, что Вы имели ввиду, что хотите разложить число на простые множители,
ведь так? Я сужу по Вашему замечанию, насчёт правильного ответа:

7 = [63, 3, 21, 3, 7] А должно: 63 = 3 * 3 * 7


Хотя, строки:

if n > 1:
   factors.append(n)
else:
   break


говорят о том, что Вы пытаетесь искать все делители.

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

Насчёт Вашего решения. Я не понимаю, зачем Вы добавляете в итоговый список текущий
делитель. Это неверно, так как добавлять в итоговый список следует лишь простые числа,
а текущий делитель, очевидно, не простой. Так что строки:

if n > 1:
   factors.append(n)
else:
   break


лишние.

Для того, чтобы получить все делители, вам нужно слегка модифицировать Ваш алгоритм:

#!/usr/bin/env python3

n = int(input("Integer: "))
factors = []
d = 2
m = n # Запомним исходное число
while d * d <= n:
        if n % d == 0:
            factors.append(d)
            n//=d
        else:
            d += 1
factors.append(n) # Добавим последнеё простое число
print('{} = {}' .format(m, factors)) # Выводим исходное число и все простые множители.


Теперь о предподсчёте с простыми числами. Легко понять, что коль скоро мы знаем все
простые числа, то выгоднее не перебирать те элементы, которые являются сами по себе
произведением простых. Т.е. будем перебирать только числа:

2, 3, 5, 7, 11, 13 ...


Числа же:

4, 6, 8, 9, 10, 12 ... 


оставим в покое, так как они являются произведением простых. Для этого, с помощью
решета Эратосфена вычислим заранее все простые до некоторого предела (2 ^ 64). После
этого полученное со входной строки число для факторизации будем раскладывать по простым
следующим образом. Делим число n до тех пор, пока оно делится на i-ое простое. Все
простые будем записывать в factors. Как только число перестаёт делиться на i-ое, берём
i+1-ое число. И так до тех пор, пока n != 1.

Спешу заметить, что хранение простых чисел, разумеется, является затратным. НО! Для
большинства задач очень подходит, так как не требуется вычислять простые числа свыше
100000000. Оперативная память современных ПК более чем позволяет хранить 1ГБ и более
данных. Простых чисел оказывается не слишком много. Согласно одной довольно известной
теореме о простых числах, их оказывается порядка n/ln(n) при возрастании n. Это означает,
что для 100000000 их будет примерно 5,3 млн, что является вполне себе допустимым. Более
того, даже 1 млрд. чисел выдержит среднестатистический ПК, так как простых числе окажется
не более 50 млн. А значит, для памяти это будет 50 млн. 4-байтовых чиселок, т.е. 200000000
байт. В мегабайтах это всего лишь 200. Так что большой проблемы в хранении нет.


Ответ 4

def factors(num, d=2):
    while num > 1:
        n1, n2 = divmod(num, d)
        if n2:
            d += 1
        else:
            yield d
            num = n1

n = int(input("Integer: "))
print('{} = {}' .format(n, ' * '.join(map(str, factors(n)))))

>>> Integer: 63
>>> 63 = 3 * 3 * 7


Ответ 5

num = int(input())
list_simple = []
simple = 2
while num > 1:
    if num % simple == 0:
        list_simple.append(simple)
        num = num/simple
    else:
        simple += 1
print(list_simple)