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

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

  • автор:

Программа разложения числа на простые множители в 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 

Python-сообщество

[RSS Feed]

  • Начало
  • » Центр помощи
  • » Разложить число на простые множители. Число находится в файле

#1 Янв. 11, 2019 17:12:00

mixa199546 Зарегистрирован: 2019-01-11 Сообщения: 7 Репутация: 0 Профиль Отправить e-mail

Разложить число на простые множители. Число находится в файле

Как сделать, чтобы число считывалось с файла

a=104 i = 2 while i  a: if a % i == 0: print(i) a /= i else: i += 1 print(a) 

Нахождение делителей числа с помощью Python

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

Делитель, также известный как фактор или множитель, — это такое целое число m, на которое n делится без остатка. Например, делителями числа 12 являются 1, 2, 3, 4, 6 и 12.

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

Простейший подход

Если мы хотим найти все числа, которые делят n без остатка, мы можем просто перебрать числа от 1 до n:

 
 
def get_all_divisors_brute(n): for i in range(1, int(n / 2) + 1): if n % i == 0: yield i yield n

На деле нам нужно дойти только до n/2, потому что все, что больше этого значения, гарантировано не может быть делителем n — если вы разделите n на что-то большее, чем n/2, результат не будет целым числом.

Этот код очень прост, и для малых значений n он работает достаточно хорошо, но он довольно неэффективен и медлителен в других случаях. По мере увеличения n время выполнения линейно увеличивается. Можем ли мы сделать лучше?

Факторизация

В моем проекте я работал в основном с факториалами. Факториал числа n, обозначаемый n! — это произведение всех целых чисел от 1 до n включительно. Например:

8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1

Поскольку факториалы состоят преимущественно из небольших множителей, я решил попробовать получить список делителей, определив сначала наименьшие из них. В частности, я искал простые множители, то есть те, которые также являются простыми числами. (Простое число — это число, единственными делителями которого являются оно само и 1. Например, 2, 3 и 5 являются простыми, а 4 и 6 — нет).

Вот функция, которая находит простые делители числа n:

 
 
def get_prime_divisors(n): i = 2 while i * i 1: yield n

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

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

8! = 2^7 × 3^2 × 5 × 7

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

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

Это дает нам способ находить делители путем перебора всех комбинаций простых множителей. Простые множители любого m делителя числа n должны входить в подмножество простых множителей n, иначе m не делило бы число n.

Переход от факторизации к делителям

Для начала разложим исходное число на простые множители с указанием «кратности», то есть мы должны получить список всех множителей и количество раз, которое каждый из них встречается в факторизации:

 
 
import collections def get_all_divisors(n): primes = get_prime_divisors(n) primes_counted = collections.Counter(primes) .

Затем, давайте продолжим и возведем каждое простое число во все степени, которые могут появиться в возможном делителе n.

 
 
def get_all_divisors(n): . divisors_exponentiated = [ [div ** i for i in range(count + 1)] for div, count in primes_counted.items() ]

Например, для 8! представленный код выдаст нам следующее:

 
 
[ [1, 2, 4, 8, 16, 32, 64, 128], // 2^0, 2^1, . 2^7 [1, 3, 9], // 3^0, 3^1, 3^2 [1, 5], [1, 7], ]

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

 
 
import itertools def calc_product(iterable): acc = 1 for i in iterable: acc *= i return acc def get_all_divisors(n): . for prime_exp_combination in itertools.product(*divisors_exponentiated): yield calc_product(prime_exp_combination)

Таким образом, мы находим все делители n (хотя, в отличие от предыдущих функций, они не отсортированы).

Собираем все вместе

Сложив все это, мы получим следующую функцию для вычисления делителей n:

 
 
import collections import itertools def get_prime_divisors(n): i = 2 while i * i 1: yield n def calc_product(iterable): acc = 1 for i in iterable: acc *= i return acc def get_all_divisors(n): primes = get_prime_divisors(n) primes_counted = collections.Counter(primes) divisors_exponentiated = [ [div ** i for i in range(count + 1)] for div, count in primes_counted.items() ] for prime_exp_combination in itertools.product(*divisors_exponentiated): yield calc_product(prime_exp_combination) print(list(get_all_divisors(40320))) # 8!

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

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

Да и для 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 . Так что большой проблемы в хранении нет.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *