Посмотрите, например, как сделано здесь. Существуют более сложные и эффективные методы. А также обратите внимание на решето Эратосфена (тут). Если вы хотите получать факторизацию не для одного числа, а для большого набора числел, то выгоднее использовать перебор по простым. Об этом я расскажу чуть ниже.
Кроме того, я думаю, что Вы имели ввиду, что хотите разложить число на простые множители, ведь так? Я сужу по Вашему замечанию, насчёт правильного ответа:
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. Так что большой проблемы в хранении нет.
how to find all factors of a number and list the factors in a list.
Input:
>>>factors(72)
Output:
[2, 2, 2, 3, 3]
I have taken some code down because this is getting a lot of views and this is a HW questions so i don’t want it copied.
asked Aug 13, 2014 at 18:12
8
def factors(n):
a = []
x = 2
while x * x <= n :
if n % x == 0:
a.append(x)
n /= x
else: x += 1
if n > 1: a.append(n)
return a
all downvoted as quickly as possible.
answered Aug 13, 2014 at 18:29
With regard to your question 1: factoring is hard. That’s why it’s at the core of many cryptographic algorithms — we currently don’t know a way to quickly factor a very large number.
For small numbers, your algorithm will do. For slightly larger numbers, I’ve had the same question — apparently Pollard’s Rho is a good algorithm for this purpose. For large numbers, we don’t know.
Now to your question 2:
First of all, in your prime(n) function, you don’t need to check if n%i==0 all the way up to n. You only need to check this up to sqrt(n), because if there is any pair of integers (a,b) such that a * b = n, then one of these integers will necessarily be less than or equal to sqrt(n). So you only need to check up to sqrt(n). This saves you a lot of computations.
Here’s your factors function:
from math import ceil
def factors(n):
factors = []
while n > 1:
for i in range(2,int((ceil(n/2.0))+1)):
if n%i==0:
factors.append(i)
n = n/i
continue
factors.append(n)
break
return factors
answered Aug 13, 2014 at 18:17
NewbNewb
2,8153 gold badges21 silver badges34 bronze badges
0
Here is a solution using decomposition by prime numbers. It is much faster.
import bisect
import math
import pathlib
primes = []
last_prime = None
def _get_primes():
"""
Load all the primes in global primes. Set global last_prime to last prime
read.
"""
global primes
global last_prime
path_to_primes = pathlib.Path(__file__).parent
.joinpath('../resources/primes.txt')
with path_to_primes.open() as file:
for line in file:
for n in line.split():
n = n.strip()
if n:
n = int(n)
primes.append(n)
last_prime = primes[-1]
def gen_primes_before(n):
"""
Generates all the primes before n in reverse order.
"""
assert n <= last_prime, "Maximum value for n is {}".format(last_prime)
pos = bisect.bisect_left(primes, n)
if pos:
yield from primes[:pos]
def gen_factors(n):
"""
Generates all the factors of a number. May return some values multiple
times. Values returned are not ordered.
"""
type_n = type(n)
assert type_n is int or (type_n is float and n.is_integer()), "Wrong type"
n = int(n)
r = int(math.sqrt(n)) + 1
assert r <= last_prime, "n is over limit"
yield 1
yield n
for prime in gen_primes_before(r):
partner = n/prime
if partner.is_integer():
yield from gen_factors(prime)
yield from gen_factors(partner)
def get_factors(n):
"""
Get all the factors of n as a sorted list.
"""
return sorted(set(gen_factors(n)))
_get_primes()
if __name__ == '__main__':
l = (1e9,)
for n in l:
print("The factors of {} are {}".format(n, get_factors(n)))
I made a repository: https://github.com/Pierre-Thibault/Factor
answered Aug 5, 2018 at 1:59
Pierre ThibaultPierre Thibault
1,8352 gold badges19 silver badges21 bronze badges
В этом руководстве мы обсудим, как получить простой множитель данного числа с помощью программы разложения числа в 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
Изучаю Python вместе с вами, читаю, собираю и записываю информацию опытных программистов.
Автор оригинала: Team Python Pool.
Вступление
В этой статье мы увидим программу python для печати всех простых множителей данного числа. Если число является простым числом и идеально делит данное число, то это число называется простым множителем данного числа. Здесь мы увидим, что такое простой фактор, метод поиска простого фактора и программа python.
Что такое простой множитель числа?
Простые множители числа-это простое число, которое при умножении вместе дает число. мы можем проверить простой множитель числа по двум условиям:
- Число должно быть простым.
- Число должно идеально делить число.
Шаги по поиску простых множителей числа
- Пусть число обозначается числом num.
- в то время как num делится на 2, мы выведем 2 и разделим num на 2.
- После шага 2 число всегда должно быть нечетным.
- Начните цикл с квадратного корня из n. Если я разделю num, выведите i и разделите num на i. После того как я не смогу разделить num, увеличьте значение i на 2 и продолжайте.
- Если num-простое число и больше 2, то num не может стать 1.
- Итак, выведите 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 различных методов. Все методы подробно объясняются с помощью примеров и их объяснения. Вы можете использовать любой метод, который вам нравится, в соответствии с вашими потребностями.
-
-
Actions
Automate any workflow
-
Packages
Host and manage packages
-
Security
Find and fix vulnerabilities
-
Codespaces
Instant dev environments
-
Copilot
Write better code with AI
-
Code review
Manage code changes
-
Issues
Plan and track work
-
Discussions
Collaborate outside of code
Explore
-
All features
-
Documentation
-
GitHub Skills
-
Blog
-
-
For
-
Enterprise
-
Teams
-
Startups
-
Education
By Solution
-
CI/CD & Automation
-
DevOps
-
DevSecOps
Case Studies
-
Customer Stories
-
Resources
-
-
-
GitHub Sponsors
Fund open source developers
-
The ReadME Project
GitHub community articles
Repositories
-
Topics
-
Trending
-
Collections
-
- Pricing
