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

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

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

number=int(input("Integer: ")) for i in range(1, number+1): if(number%i==0): print(i) 

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

#!/usr/bin/env python3 n=int(input("Integer: ")) factors = [] d = 2 while d * d 1: factors.append(n) else: break print('<> = <>' .format(n,factors)) 

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

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

Ответы (5 шт):

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

def primfacs(n): i = 2 primfac = [] while i * i 1: primfac.append(n) return primfac 

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 

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

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

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 ^ 64 ). После этого полученное со входной строки число для факторизации будем раскладывать по простым следующим образом. Делим число n до тех пор, пока оно делится на i -ое простое. Все простые будем записывать в factors . Как только число перестаёт делиться на i -ое, берём i+1 -ое число. И так до тех пор, пока n != 1 .

Спешу заметить, что хранение простых чисел, разумеется, является затратным. НО! Для большинства задач очень подходит, так как не требуется вычислять простые числа свыше 100000000 . Оперативная память современных ПК более чем позволяет хранить 1ГБ и более данных. Простых чисел оказывается не слишком много. Согласно одной довольно известной теореме о простых числах, их оказывается порядка n/ln(n) при возрастании n . Это означает, что для 100000000 их будет примерно 5,3 млн , что является вполне себе допустимым. Более того, даже 1 млрд. чисел выдержит среднестатистический ПК, так как простых числе окажется не более 50 млн . А значит, для памяти это будет 50 млн . 4-байтовых чиселок, т.е. 200000000 байт . В мегабайтах это всего лишь 200 . Так что большой проблемы в хранении нет.

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

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: Но вообще вариант с циклом из соседнего ответа лучше.

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) 

Источник

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

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

Вступление

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

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

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

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

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

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

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

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

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

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

# python program to print prime factors import math def primefactors(n): #even number divisible while n % 2 == 0: print (2), n = n / 2 #n became odd for i in range(3,int(math.sqrt(n))+1,2): while (n % i == 0): print (i) n = n / i if n > 2: print (n) n = int(input("Enter the number for calculating the prime factors :\n")) primefactors(n)

Enter the number for calculating the prime factors : 650 2 5 5 13

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

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

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

#using for loop n = int(input("Enter the number for calculating the prime factors :\n")) for i in range(2,n + 1): if n % i == 0: count = 1 for j in range(2,(i//2 + 1)): if(i % j == 0): count = 0 break if(count == 1): print(i)

Enter the number for calculating the prime factors : 350 2 5 7

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

NOTE: Suppose we take input as 650 : the prime factors are 2,5,5,13 so, it will print 2,5,13 as all integers one time.

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

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

#using while loop n = int(input("Enter any Number for calculating the prime factors: ")) i = 1 while(i 
Enter any Number for calculating the prime factors: 350 2 5 7
 
В этом примере мы будем использовать только цикл while. Во-первых, мы приняли входные данные от пользователя как n. Во-вторых, мы установим значение i как 1. В-третьих, мы применим цикл while с условием проверки, так как i должен быть меньше или равен n. Внутри цикла | мы установим значение c равным 0 и применим в нем условие if и while. Наконец, мы проверим, станет ли значение c равным 2, а затем выведем значение i. Следовательно, простые множители печатаются с единственным-единственным их значением.
 
NOTE: Suppose we take input as 650 : the prime factors are 2,5,5,13 so, it will print 2,5,13 as all integers one time.
 
Вывод
 
В этом уроке мы видели, как найти простые множители числа с помощью 3 различных методов. Все методы подробно объясняются с помощью примеров и их объяснения. Вы можете использовать любой метод, который вам нравится, в соответствии с вашими потребностями.
 
Источник
 
Разложение на простые множители
 
Разложение на простые множители
Требуется разложить целое число N на простые множители и вывести результат в порядке возрастания.
 
Разложение на простые множители
Разложение на простые множители Требуется разложить целое число N на простые множители с учётом их.
 
Разложение на простые множители (Время: 1 сек. Память: 16 Мб Сложность: 27%)
Требуется вывести представление целого числа N в виде произведения простых чисел. Входные данные.
 
 
 Разложение на множители
Задача разложения числа на простые(!) множители решается многими методами и довольно быстро.
 
Разложение на множители
Добрый день. Нужно разложить число на множители в виде: 24=2*2*2*2*3. Но в программе получается.
 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
 
def factorization(n): p = [] d = 2 while d * d  n: while n % d == 0: p.append(d) n //= d d += 1 if n > 1: p.append(n) return p a = factorization(int(input())) b = [] a.reverse() for i in a: if i not in b: print(f'^') b.append(i)
 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
 
def factorization(n): p = [] d = 2 while d * d  n: while n % d == 0: p.append(d) n //= d d += 1 if n > 1: p.append(n) return p n = int(input()) a = factorization(n) a.reverse() b = [] str1 = str(n) + ' =' for i in a: if i not in b: str1 += f' ^ +' b.append(i) print(str1[:-1])
 
Источник