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

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=p₁^s₁·<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 на простые множители, в котором одинаковые сомножители объединены в степени.

Пример

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

Это представление натурального числа a ? 1 в виде произведения простых чисел.