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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

оставим в покое, так как они являются произведением простых. Для этого, с помощью решета Эратосфена вычислим заранее все простые до некоторого предела ( 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 . Так что большой проблемы в хранении нет.

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

В задачах ЕГЭ по информатике часто требуется находить множители числа и проверять, является ли данное число простым. Рассмотрим способы делать это достаточно быстро.

Разложение на множители.

Самый простой способ разложения числа на множители: проверить его делимость на все числа, начиная с 2 и кончая числом, равным половине исходного. Но этот способ — слишком медленный.

Ускорить процедуру можно, если учесть тот факт, что если число n делится на число k, то оно делится и на n//k. Тогда можно проверить лишь числа от 2 до квадратного корня из n. Когда мы находим число k, на которое делится число n, то добавляем в список делителей два делителя: k и n//k. Один тонкий момент: если число n является точным квадратом числа k, то и k, и n//k — это одинаковые числа. Поэтому нужно ввести проверку и добавлять в список делителей n//k только в том случае, если это число не равно k. Тем самым мы избежим включения в массив делителей двух одинаковых чисел.

Приведем текст функции на Питоне, которая вычисляет все делители числа n, кроме единицы и самого числа n (так называемые нетривиальные делители) и возвращает массив, содержащий эти делители.

def divisors(n):
d=[]
k=2
while k*k <= n:
if n%k == 0:
d.append(k)
k2 = n//k
if k2 > k: d.append(k2)
k += 1
return d

Условие k*k <= n прекращает выполнение цикла поиска делителей, когда k станет больше, чем квадратный корень из n. Почему мы записали его так, а не в виде k<=sqrt(n)? На это есть две причины.

Во-первых, операция умножения выполняется гораздо быстрее, чем извлечение корня. Во-вторых, функция извлечения корня возвращает вещественный результат. А операции над вещественными числами выполняются лишь приближенно, и квадратный корень из 4 при вычислениях может оказаться равным 2.0000000001, а может и 1.9999999999. Понятно, что это может сказаться на результате сравнения самым пагубным образом.

Делители в массиве не упорядочены по возрастанию. Так, для числа 60 получается следующий результат:

[2, 30, 3, 20, 4, 15, 5, 12, 6, 10]

Если требуется упорядоченность, то нужно либо отсортировать полученный массив, либо вставлять делители в массив, поддерживая его упорядоченность (например, с помощью функции insort из модуля bisect).

Проверка числа на простоту.

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

Читать:

Long polling что это

Но можно написать для этой цели и отдельную функцию. Приведем её текст:

def isprime(n):
k=2
while k*k <= n:
if n%k == 0: return False
k += 1
return True

Функция возвращает True, если число n — простое.

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

Существуют и более быстрые алгоритмы для решения данных задач, но они достаточно сложны, и на ЕГЭ их не имеет смысла применять.

Name already in use

6115-preparation-for-the-credit-Python-3-semester / 16. Разложение числа на множители.py /

Go to file T
Go to line L
Go to definition R
Copy path
Copy permalink

Open with Desktop
View raw
Copy raw contents Copy raw contents

Copy raw contents

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

Простая факторизация | Как найти простые множители числа в Python

Если число является простым числом и идеально делит данное число, то это число называется простым множителем python данного числа.

Автор записи

Вступление

В этой статье мы увидим программу python для печати всех простых множителей данного числа. Если число является простым числом и идеально делит данное число, то это число называется простым множителем данного числа. Здесь мы увидим, что такое простой фактор, метод поиска простого фактора и программа python.

Что такое простой множитель числа?

Простые множители числа-это простое число, которое при умножении вместе дает число. мы можем проверить простой множитель числа по двум условиям:

Число должно быть простым.
Число должно идеально делить число.

Шаги по поиску простых множителей числа

Пусть число обозначается числом num.
в то время как num делится на 2, мы выведем 2 и разделим num на 2.
После шага 2 число всегда должно быть нечетным.
Начните цикл с квадратного корня из n. Если я разделю num, выведите i и разделите num на i. После того как я не смогу разделить num, увеличьте значение i на 2 и продолжайте.
Если num-простое число и больше 2, то num не может стать 1.
Итак, выведите num, если он больше 2.

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

Давайте разберемся в программе для простых множителей числа подробнее с помощью различных примеров:

1. Простой множитель числа в Python с использованием циклов While и for

В этой программе мы будем использовать цикл while и цикл for как для определения простых множителей данного числа. мы импортируем математический модуль в эту программу, чтобы использовать функцию квадратного корня в python. После этого мы применим цикл и попытаемся найти простые множители данного числа.

Здесь сначала мы импортировали математическую библиотеку из модуля python. Во-вторых, мы взяли вход n в качестве числа и вызвали функцию primefactors() . В-третьих, мы взяли primefactors() в качестве функции и применили цикл while и проверили, идет ли модуль числа 0, разделив его на 2. В-четвертых, цикл while будет выполняться до тех пор, пока число не станет четным и делимым на 2, и выводить его и делить число на 2 на каждой итерации. После этого мы применим цикл for от ‘ до квадратного корня из n+1. Затем мы снова применим цикл while внутри цикла for и проверим условие. Наконец, если n больше 2, то мы напечатали это число. Следовательно, все простые множители числа печатаются.

2. использование только для цикла

В этой программе мы будем использовать цикл for только для нахождения простых множителей данного числа. мы будем применять несколько циклов for и попытаемся найти простые множители данного числа.

В этом примере мы будем использовать только цикл for. Во-первых, мы приняли входные данные от пользователя как n. Во – вторых, мы применили цикл for от до+1. Затем мы проверим, равен ли модуль значения i и числа 0. Затем мы ведем счет и снова применяем цикл for внутри цикла for от до//2+1. и проверьте данное условие if. если условие удовлетворяет, то значение count устанавливается равным 0, и мы разрываем оператор. Затем мы выходим из цикла for и проверяем условие if count и печатаем значение i. Следовательно, простые множители печатаются с единственным-единственным их значением.

3. Простой Множитель Числа В Python, использующий только цикл while

В этой программе мы будем использовать цикл while только для определения простых множителей данного числа. мы будем применять несколько циклов while и попытаемся найти простые множители данного числа.

В этом примере мы будем использовать только цикл while. Во-первых, мы приняли входные данные от пользователя как n. Во-вторых, мы установим значение i как 1. В-третьих, мы применим цикл while с условием проверки, так как i должен быть меньше или равен n. Внутри цикла | мы установим значение c равным 0 и применим в нем условие if и while. Наконец, мы проверим, станет ли значение c равным 2, а затем выведем значение i. Следовательно, простые множители печатаются с единственным-единственным их значением.

Вывод

В этом уроке мы видели, как найти простые множители числа с помощью 3 различных методов. Все методы подробно объясняются с помощью примеров и их объяснения. Вы можете использовать любой метод, который вам нравится, в соответствии с вашими потребностями.