Посмотрите, например, как сделано здесь. Существуют более сложные и эффективные методы. А также обратите внимание на решето Эратосфена (тут). Если вы хотите получать факторизацию не для одного числа, а для большого набора числел, то выгоднее использовать перебор по простым. Об этом я расскажу чуть ниже.
Кроме того, я думаю, что Вы имели ввиду, что хотите разложить число на простые множители, ведь так? Я сужу по Вашему замечанию, насчёт правильного ответа:
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
. Так что большой проблемы в хранении нет.
factors.append(n)
лишнее, достаточноif n = 1: break
while
никакого условия не нужно, т.е. простоwhile true
(ну илиdo
, если такое есть в питоне). Иначе этот код на обычную тройку ничего не выведет...