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

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

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

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

В этом руководстве мы обсудим, как получить простой множитель данного числа с помощью программы разложения числа в 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 <= sqrt(n} or q <= sqrt(n) 

• 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 <= n: 
        if n % i: 
            i += 1 
        else: 
            n //= i 
    return n 
 
print(largest_prime_factor(345)) 

Выход:

23 

Автор оригинала: Team Python Pool.

Вступление

В этой статье мы увидим программу 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.

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

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 <= n):
    c = 0
    if(n % i == 0):
        j = 1
        while(j <= i):
            if(i % j == 0):
                c = c + 1
            j = j + 1
            
        if (c == 2):
            print(i)
    i = i + 1

Выход:

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 различных методов. Все методы подробно объясняются с помощью примеров и их объяснения. Вы можете использовать любой метод, который вам нравится, в соответствии с вашими потребностями.

def primes(n):
    divisors = [ d for d in range(2,n//2+1) if n % d == 0 ]
    return [ d for d in divisors if 
         all( d % od != 0 for od in divisors if od != d ) ]

Use an example, say n = 12
divisors will be the following list [2, 3, 4, 6]

Now the return part is a bit tricky and for good reason, one shouldn’t be abusing list comprehension in such a way.

So lets turn this part into an actual loop:

ans = []
for d in divisors:
    for od in divisors:
        if od != d:
            if d % od == 0:
                break
    else: ans.append(d)
return ans

Yes the else is in the right spot

Continuing with the example, what this part does is to search through the list of divisors and to see if any of them is divisible by any of the others. If this is so, we ignore that one, otherwise we keep it.

The end result is a list of prime factors.

I also mentioned in my comment that the divisors list can also be generated using:

divisors = [2] + [ d for d in xrange(3,int(n**2+1), 2) if n % d == 0]

This method is useful because it avoids including even numbers except 2, which is the only even prime. Also the size of divisors is smaller because we only check up to the square root of a number which is most times smaller than the number divided by 2