Содержание
5 ответов 5
Текущие По дате публикации Голоса5
Эта задача называется Факторизация целых чисел
Одна из реализаций(взято с 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
Улучшить ответ13
В коде есть два существенных момента, из-за которых он ищет все делители вместо факторизации. Добавлю ещё одно изменение ради оптимизации и получится такой код:
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: Но вообще вариант с циклом из соседнего ответа лучше.
Улучшить ответ41
Посмотрите, например, как сделано здесь. Существуют более сложные и эффективные методы. А также обратите внимание на решето Эратосфена (тут). Если вы хотите получать факторизацию не для одного числа, а для большого набора числел, то выгоднее использовать перебор по простым. Об этом я расскажу чуть ниже.
Кроме того, я думаю, что Вы имели ввиду, что хотите разложить число на простые множители, ведь так? Я сужу по Вашему замечанию, насчёт правильного ответа:
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
. Так что большой проблемы в хранении нет.
Улучшить ответ5
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
Улучшить ответ
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)
Улучшить ответ
Что значит разложить число на простые множители?
Разберем понятие простые множители. Известно, что каждый простой множитель – это простое число. В произведении вида <math><mn>2</mn><mo>·</mo><mn>7</mn><mo>·</mo><mn>7</mn><mo>·</mo><mn>23</mn></math> имеем, что у нас <math><mn>4</mn></math> простых множителя в виде <math><mn>2</mn><mo>,</mo><mn>7</mn><mo>,</mo><mn>7</mn><mo>,</mo><mn>23</mn></math>.
Разложение на множители предполагает его представление в виде произведений простых. Если нужно произвести разложение числа <math><mn>30</mn></math>, тогда получим <math><mn>2</mn><mo>,</mo><mn>3</mn><mo>,</mo><mn>5</mn></math>. Запись примет вид <math><mn>30</mn><mo>=</mo><mn>2</mn><mo>·</mo><mn>3</mn><mo>·</mo><mn>5</mn></math>. Не исключено, что множители могут повторяться. Такое число как <math><mn>144</mn></math> имеет <math><mn>144</mn><mo>=</mo><mn>2</mn><mo>·</mo><mn>2</mn><mo>·</mo><mn>2</mn><mo>·</mo><mn>2</mn><mo>·</mo><mn>3</mn><mo>·</mo><mn>3</mn></math>.
Не все числа предрасположены к разложению. Числа, которые больше <math><mn>1</mn></math> и являются целыми можно разложить на множители. Простые числа при разложении делятся только на <math><mn>1</mn></math> и на самого себя, поэтому невозможно представить эти числа в виде произведения.
При <math><mi>z</mi></math>, относящемуся к целым числам, представляется в виде произведения <math><mi>а</mi></math> и <math><mi>b</mi></math>, где <math><mi>z</mi></math> делится на <math><mi>а</mi></math> и на <math><mi>b</mi></math>. Составные числа раскладывают на простые множители при помощи основной теоремы арифметики. Если число больше <math><mn>1</mn></math>, то его разложение на множители <math><msub><mi>p</mi><mn>1</mn></msub><mo>,</mo><mo> </mo><msub><mi>p</mi><mn>2</mn></msub><mo>,</mo><mo> </mo><mo>…</mo><mo>,</mo><mo> </mo><msub><mi>p</mi><mi>n</mi></msub></math>принимает вид <math><mi>a</mi><mo>=</mo><msub><mi>p</mi><mn>1</mn></msub><mo>,</mo><mo> </mo><msub><mi>p</mi><mn>2</mn></msub><mo>,</mo><mo> </mo><mo>…</mo><mo>,</mo><mo> </mo><msub><mi>p</mi><mi>n</mi></msub></math>. Разложение предполагается в единственном варианте.
Каноническое разложение числа на простые множители
При разложении множители могут повторяться. Их запись выполняется компактно при помощи степени. Если при разложении числа а имеем множитель <math><msub><mi>p</mi><mn>1</mn></msub></math>, который встречается <math><msub><mi>s</mi><mn>1</mn></msub></math> раз и так далее <math><msub><mi>p</mi><mi>n</mi></msub><mo> </mo><mo>–</mo><mo> </mo><msub><mi>s</mi><mi>n</mi></msub></math> раз. Таким образом разложение примет вид a=p1s1·<math><mi>a</mi><mo>=</mo><msub><msub><mi>p</mi><msup><mn>1</mn><mi>s</mi></msup></msub><mn>1</mn></msub><mo>·</mo><msub><msub><mi>p</mi><msup><mn>2</mn><mi>s</mi></msup></msub><mn>2</mn></msub><mo>·</mo><mo>…</mo><mo>·</mo><msub><msub><mi>p</mi><msup><mi>n</mi><mi>s</mi></msup></msub><mi>n</mi></msub></math>. Эта запись имеет название канонического разложения числа на простые множители.
При разложении числа <math><mn>609840</mn></math> получим, что <math><mn>609</mn><mo> </mo><mn>840</mn><mo>=</mo><mn>2</mn><mo>·</mo><mn>2</mn><mo>·</mo><mn>2</mn><mo>·</mo><mn>2</mn><mo>·</mo><mn>3</mn><mo>·</mo><mn>3</mn><mo>·</mo><mn>5</mn><mo>·</mo><mn>7</mn><mo>·</mo><mn>11</mn><mo>·</mo><mn>11</mn></math>,его канонический вид будет <math><mn>609</mn><mo> </mo><mn>840</mn><mo>=</mo><msup><mn>2</mn><mn>4</mn></msup><mo>·</mo><msup><mn>3</mn><mn>2</mn></msup><mo>·</mo><mn>5</mn><mo>·</mo><mn>7</mn><mo>·</mo><msup><mn>11</mn><mn>2</mn></msup></math>. При помощи канонического разложения можно найти все делители числа и их количество.
Калькулятор разложения чисел на простые множители
КалькуляторПример
Основная теорема арифметики: каждое натуральное число, отличное от 1, может быть разложено на простые множители, при этом единственным образом.
Каноническое разложение числа a – разложение a на простые множители, в котором одинаковые сомножители объединены в степени.
Пример
20 = 22 • 5; 84 = 22 • 3 • 7; 800 = 25 • 52. |
Разложение чисел на простые множители
Это представление натурального числа a ? 1 в виде произведения простых чисел.