Как в питоне разложить число на множители

Программа разложения числа на простые множители в Python

В этом руководстве мы обсудим, как получить простой множитель данного числа с помощью программы разложения числа в Python. Все мы знакомы с простыми числами – это числа, которые можно разделить на единицу или на себя. Например – 1, 2, 3, 5, 7, 11, 13, ……

Нахождение всех простых множителей числа

Если пользователь вводит число как 12, то на выходе должно быть 2, 2, 3, а если на входе 315 – выход должен быть «3 3 5 7». Программа должна вернуть все простые множители данного числа. Простые множители 330 – это 2, 3, 5 и 11. Следовательно, 11 является наиболее значимым простым множителем 330.

Например: 330 = 2 × 3 × 5 × 11.

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

• 1-я гипотеза – может быть хотя бы один простой множитель, который будет меньше √n в случае, если n не является простым числом.

Доказательство. Существуют два больших числа sqrt(n), их произведение также должно делить n, но оно будет превышать n, что противоречит нашему предположению. Таким образом, не может быть более одного простого множителя n, большего, чем sqrt(n).

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

p or q 

  
2-я гипотеза – может быть более 1 простого множителя n больше, чем sqrt(n).

Доказательство. Предположим, что есть два больших числа sqrt(n), тогда их произведение также должно делить n, но оно будет больше n, что противоречит нашему предположению. Таким образом, не может быть более одного простого множителя n, большего, чем sqrt(n).
Давайте посмотрим на следующий шаг, чтобы выполнить такую операцию.






Пример – программа Python для печати простых множителей.
import math # Below function will print the # all prime factor of given number def prime_factors(num): # Using the while loop, we will print the number of two's that divide n while num % 2 == 0: print(2,) num = num / 2 for i in range(3, int(math.sqrt(num)) + 1, 2): # while i divides n , print i ad divide n while num % i == 0: print(i,) num = num / i if num > 2: print(num) # calling function num = 200 prime_factors(num)
2 2 2 5 5
В приведенном выше коде мы импортировали математический модуль. Функция prime_factor() отвечает за печать составного числа. Сначала мы получаем четные числа; после этого все оставшиеся простые множители должны быть нечетными. В цикле for число должно быть нечетным, поэтому мы увеличили i на два. Цикл for будет вычислять квадратный корень n раз.
Давайте разберемся в следующем свойстве составных чисел.
Каждое составное число имеет хотя бы один простой множитель, меньший или равный квадратному корню.






Программа будет работать следующим образом:

На первом шаге найдем наименьший простой множитель i.
Вхождение i будет удалено из n путем многократного деления n на i.
Повторим оба вышеуказанных шага для деления n и i = i + 2. Оба шага будут повторяться до тех пор, пока n не станет либо 1, либо простым числом.

Давайте разберемся в другом примере, где мы находим наибольший простой множитель данного числа.
Пример – 2: Программа Python для определения наибольшего простого множителя заданного числа.
def largest_prime_factor(n): i = 2 while i * i 

Разложить число на простые множители
Да и для while никакого условия не нужно, т.е. просто while true (ну или do , если такое есть в питоне). Иначе этот код на обычную тройку ничего не выведет.






30 мар 2017 в 9:32
5 ответов 5
Сортировка: Сброс на вариант по умолчанию
Одна из реализаций(взято с OEIS#A238724):
def primfacs(n): i = 2 primfac = [] while i * i 1: primfac.append(n) return primfac 
Отслеживать

ответ дан 28 мар 2017 в 13:44

27.2k 2 2 золотых знака 45 45 серебряных знаков 76 76 бронзовых знаков

29 мар 2017 в 3:38
В коде есть два существенных момента, из-за которых он ищет все делители вместо факторизации. Добавлю ещё одно изменение ради оптимизации и получится такой код:
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: Но вообще вариант с циклом из соседнего ответа лучше.






Отслеживать

ответ дан 31 мар 2017 в 11:25

123k 24 24 золотых знака 128 128 серебряных знаков 307 307 бронзовых знаков
"случай, что само число было простым" В number всегда будет последний простой делитель(кроме случая, когда на входе была единица).
31 мар 2017 в 11:49






@vp_arth, нет, во всех остальных случаях там 1. Мы же делим на каждый простой делитель до корня, пока они не кончатся.
31 мар 2017 в 11:50

ок, не всегда, иногда там 1. Однако, 51 => range(2, 8) => 3, 17!

31 мар 2017 в 12:00
@vp_arth, да, понял. Поменял комментарий. Если хочешь, можешь ещё сам поправить что-нибудь. Но код-то верный во втором варианте.
31 мар 2017 в 14:02






Посмотрите, например, как сделано здесь. Существуют более сложные и эффективные методы. А также обратите внимание на решето Эратосфена (тут). Если вы хотите получать факторизацию не для одного числа, а для большого набора числел, то выгоднее использовать перебор по простым. Об этом я расскажу чуть ниже.
Кроме того, я думаю, что Вы имели ввиду, что хотите разложить число на простые множители, ведь так? Я сужу по Вашему замечанию, насчёт правильного ответа:
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 = <>' .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 . Так что большой проблемы в хранении нет.
Разложение числа на простые множители с помощью решета Эратосфена.
 
Дано натуральное число N (> 1). Написать программу на Python, которая будет выполнять разложение числа N на простые множители, используя для этого усовершенствованный алгоритм решета Эратосфена. Программа должна выводить список простых множителей числа N в порядке возрастания. Если число является простым, программа должна вернуть N. Учитывайте, что множители могут повторяться (например, для числа 12 список множителей будет 2, 2, 3).






Код Python: def sieve_eratosthenes(n): sieve = [True] * (n + 1) for p in range(2, int(n ** 0.5) + 1): if sieve[p]: for i in range(p * p, n + 1, p): sieve[i] = False return [p for p in range(2, n + 1) if sieve[p]] def prime_factorization(n): primes = sieve_eratosthenes(n) prime_factors = [] for prime in primes: while n % prime == 0: prime_factors.append(prime) n //= prime if n == 1: break return prime_factors if prime_factors else [n] # Пример использования number = 315 factors = prime_factorization(number) print(factors)
Алгоритм сначала генерирует все простые числа до N, используя решето Эратосфена. Затем последовательно делит исходное число N на найденные простые числа до тех пор, пока деление не будет без остатка. Каждый простой делитель добавляется в список простых множителей. Если после окончания процесса остаётся число больше 1, которое не разделилось наизвестные простые числа, оно также является простым множителем. Сложность данного алгоритма определяется качеством реализации решета Эратосфена и логикой последовательного деления числа N на простые множители.
Похожие записи:

Факторизация
Декораторы в Python
Unittest в Django: тестирование URLs
Решето Эратосфена

Разложение числа на простые множители (факторизация). Делители числа
Представление числа в виде произведения простых множителей
Из различных разделов математики в спортивном программировании чаще всего встречаются элементы элементарной теории чисел. В этом разделе значительную роль имеет разложение числа на простые множители. Простыми называются такие числа, которые не имеют делителей кроме 1 и самого себя. Ряд простых чисел выглядит так:
\[2, 3, 5, 7, 11, 13, 17, 19, 23, \ldots\]
Все остальные натуральные числа (кроме 1) называются составными, так как их можно представить в виде произведения нескольких простых чисел. Например:






Часто это записывается со степенями простых множителей:
Таким образом, любое число можно представить в виде произведения простых множителей следующим образом:
Согласно основной теореме арифметики, каждому числу однозначно соответствует такое представление, поэтому разложение числа на простые множители тесно связано с некоторыми его свойствами, и часто используется в решении задач.






Проверка числа на простоту
Чтобы проверить, является ли натуральное число \(x\) простым, достаточно просто проверить, существует ли в отрезке \([2;\sqrt]\) число, на которое делится \(x\). Это достаточно очевидно: если бы существовало такое число \(y\), что \(x\) делится на \(y\) и \(\sqrt < y < x\), то гарантированно существовало бы и число \(z = x/y\), которое было бы меньше корня, а значит, изначального условия хватило бы для проверки на простоту.
Реализация на C++:
1 2 3 4 5 6 7 8 9
bool is_prime(int x)  for (int i = 2; i  sqrt(x); i++)  if (x % i == 0)  return false; > > return true; > 
Сложность этого алгоритма \(O(\sqrt)\). Существуют алгоритмы, позволяющие выполнять эту проверку быстрее (порядка \(O(\log^6 N)\)), но они исключительно редко применяются в спортивном программировании.
Факторизация
Факторизацией называется разложение числа на простые множители. Алгоритм факторизации основывается на тех же идеях, что и алгоритм проверки на простоту, приведённый выше. А именно: если у числа существует простой делитель, отличный от него самого, то он не превышает корня из числа. Для факторизации числа нужно перебрать все числа в промежутке \([2;\sqrt]\), и попытаться разделить \(x\) на каждое из них по очереди.






Реализация на C++ (Сложность: \(O(\sqrt)\)):
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
vectorint> factorize(int x)  vectorint> factors; for (int i = 2; i  sqrt(x); i++)  while (x % i == 0)  factors.push_back(i); x /= i; > > if (x != 1)  factors.push_back(x); > return factors; > 
Корректность этого алгоритма доказать также несложно. Заметим, что если при факторизации числа \(x\) мы нашли делитель \(y\), то нам, по факту, осталось факторизовать число \(x/y\). Поэтому мы можем смело разделить число \(x\) на \(y\) и продолжить работу алгоритма. Мы можем не начинать проверку сначала, так как число \(x/y\) гарантированно не имеет делителей меньше \(y\), иначе мы бы их уже нашли при факторизации \(x\).
Также очевидно, что все множители, найденные алгоритмом будут простыми. Можно заметить, что каждый раз алгоритм находит минимальный из всех делителей числа, и делит на него само число. Минимальный возможный делитель числа всегда будет простым.
И наконец, используя доказательство из предыдущего раздела, если у числа нет делителей меньше либо равных его корню, то оно простое. Этот случай обрабатывается отдельной проверкой после цикла.






Также можно реализовать алгоритм в виде поиска пар \((p_i, \alpha_i)\), где \(p_i\) - множитель, \(\alpha_i\) - его степень:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
mapint, int> factorize(int x)  mapint, int> factors; for (int i = 2; i  sqrt(x); i++)  while (x % i == 0)  factors[i]++; x /= i; > > if (x != 1)  factors[x]++; > return factors; > 
Поиск делителей
Поиск делителей числа и разложение его на множители - разные понятия, хотя термины в какой-то степени схожи. Под делителями числа подразумевают все числа, на которые оно делится. Пример для числа 20:



Множители
\(2, 2, 5\)


Делители
\(1, 2, 4, 5, 10, 20\)



Алгоритм поиска делителей числа \(x\) во многом похож на другие алгоритмы, приведённые выше. Мы рассматриваем делители парами: для каждого делителя \(y\) мы учитываем соответствующий ему \(x/y\). Один из этих делителей гарантированно не превышает \(\sqrt\), поэтому, как и раньше, мы можем рассматривать только промежуток \([1;\sqrt]\).
Реализация на C++ (Сложность: \(O(\sqrt)\)):






1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
vectorint> find_dividers(int x)  vectorint> dividers; for (int i = 1; i  sqrt(x); i++)  if (x % i == 0)  dividers.push_back(i); //для корня из x не существует парного делителя if (i * i != x)  dividers.push_back(x / i); > > > return dividers; > 
Количество делителей
В качестве примера математических свойств представления числа в виде простых множителей приведём связь между характеристиками простых множителей числа и количеством его делителей.
Для этого давайте определим понятие делителя в контексте простых множителей. Запишем числа \(x\) и \(y\) в следующем виде:
Если какой-либо простой множитель не входит в разложение одного из чисел, то его степень в следующих рассуждениях принимается за 0.






Утверждение: частное двух чисел можно записать следующим образом:
Так как мы работаем с натуральными числами, это выражение имеет смысл тогда и только тогда, когда все степени простых множителей целые и неотрицательные. Отсюда можно выразить условие делимости двух чисел:
\[\forall i: \alpha_i - \beta_i \ge 0\]
\[\forall i: \beta_i \le \alpha_i\]
(Если вы не знакомы с подобной записью, \(\forall i\) обозначает “для всех \(i\)”)
Из этого условия можно легко вывести количество делитей. Ещё раз запишем \(x\) в виде
Вспомним, что любому натуральному числу однозначно соответствует разложение на простые множители, то есть, набор степеней. Другими словами, изменение любой степени в наборе даст нам новое уникальное число.
Давайте рассмотрим, сколько возможных значений может принимать каждая степень \(\beta_i\). С ней связано два условия:
\(\beta_i \ge 0\) 
\(\beta_i \le \alpha_i\)
Значит, каждая из степеней \(\beta_i\) может принимать \(\alpha_i + 1\) различных значений, и набор степеней \(\beta\) однозначно описывает уникальный делитель. Используя формулы комбинаторики мы можем выразить количество делителей следующим образом:
\[K = (\alpha_1 + 1) * (\alpha_2 + 1) * \ldots * (\alpha_n + 1) = \prod\limits_i (\alpha_i + 1)\]
Реализация на C++:
1 2 3 4 5 6 7 8 9
int dividers_count(mapint, int>& factors)  int result = 1; for (mapint, int>::iterator it = factors.begin(); it != factors.end(); it++)  result *= it->second + 1; > return result; > 
Реализация на C++11:
1 2 3 4 5 6 7 8 9
int dividers_count(mapint, int>& factors)  int result = 1; for (auto p: factors)  result *= p.second + 1; > return result; > 
Это всего лишь одно из свойств простых множителей. Единственный способ научиться решать задачи на эту тему - практика.
brestprog
Олимпиадное программирование в Бресте и Беларуси


Похожие публикации:

Как включить камеру на компьютере
Перфоратор bosch или makita что лучше
Телеграмм как установить на компьютер
Телефон как bluetooth адаптер для компьютера