Python 素数分解 - 列表
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/16996217/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Prime factorization - list
提问by Snarre
I am trying to implement a function primeFac()that takes as input a positive integer nand returns a list containing all the numbers in the prime factorization of n.
我正在尝试实现一个函数primeFac()，该函数将一个正整数作为输入n并返回一个包含n.
I have gotten this far but I think it would be better to use recursion here, not sure how to create a recursive code here, what would be the base case? to start with.
我已经走了这么远，但我认为在这里使用递归会更好，不确定如何在这里创建递归代码，基本情况是什么？开始。
My code:
我的代码：
def primes(n):
primfac = []
d = 2
while (n > 1):
if n%d==0:
primfac.append(d)
# how do I continue from here... ?
采纳答案by Daniel Fischer
A simple trial division:
一个简单的试验划分：
def primes(n):
primfac = []
d = 2
while d*d <= n:
while (n % d) == 0:
primfac.append(d) # supposing you want multiple factors repeated
n //= d
d += 1
if n > 1:
primfac.append(n)
return primfac
with O(sqrt(n))complexity (worst case). You can easily improve it by special-casing 2 and looping only over odd d(or special-casing more small primes and looping over fewer possible divisors).
具有O(sqrt(n))复杂性（最坏的情况）。您可以通过特殊情况 2 并仅循环奇数d（或特殊情况下更多的小素数并循环更少的可能除数）来轻松改进它。
回答by Ashwini Chaudhary
You can use sieve Of Eratosthenesto generate all the primes up to (n/2) + 1and then use a list comprehension to get all the prime factors:
您可以使用sieve Of Eratosthenes生成所有素数(n/2) + 1，然后使用列表理解来获取所有素数：
def rwh_primes2(n):
# http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
""" Input n>=6, Returns a list of primes, 2 <= p < n """
correction = (n%6>1)
n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
sieve = [True] * (n/3)
sieve[0] = False
for i in xrange(int(n**0.5)/3+1):
if sieve[i]:
k=3*i+1|1
sieve[ ((k*k)/3) ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]
def primeFacs(n):
primes = rwh_primes2((n/2)+1)
return [x for x in primes if n%x == 0]
print primeFacs(99999)
#[3, 41, 271]
回答by deufeufeu
This is a comprehension based solution, it might be the closest you can get to a recursive solution in Python while being possible to use for large numbers.
这是一个基于理解的解决方案，它可能是您在 Python 中最接近递归解决方案的方法，同时也可以用于大量数字。
You can get proper divisors with one line:
您可以通过一行获得适当的除数：
divisors = [ d for d in xrange(2,int(math.sqrt(n))) if n % d == 0 ]
then we can test for a number in divisors to be prime:
然后我们可以测试一个除数中的数是否为素数：
def isprime(d): return all( d % od != 0 for od in divisors if od != d )
which tests that no other divisors divides d.
它测试没有其他除数可整除 d.
Then we can filter prime divisors:
然后我们可以过滤素数：
prime_divisors = [ d for d in divisors if isprime(d) ]
Of course, it can be combined in a single function:
当然，它可以组合在一个函数中：
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 ) ]
Here, the \ is there to break the line without messing with Python indentation.
在这里， \ 可以在不干扰 Python 缩进的情况下断行。
回答by user448810
Here is my version of factorization by trial division, which incorporates the optimization of dividing only by two and the odd integers proposed by Daniel Fischer:
这是我的试除法分解版本，它结合了仅除以二的优化和 Daniel Fischer 提出的奇数整数：
def factors(n):
f, fs = 3, []
while n % 2 == 0:
fs.append(2)
n /= 2
while f * f <= n:
while n % f == 0:
fs.append(f)
n /= f
f += 2
if n > 1: fs.append(n)
return fs
An improvement on trial division by two and the odd numbers is wheel factorization, which uses a cyclic set of gaps between potential primes to greatly reduce the number of trial divisions. Here we use a 2,3,5-wheel:
对二分法和奇数的试除法的改进是轮因式分解，它使用潜在素数之间的一组循环间隙来大大减少试除法的次数。这里我们使用 2,3,5 轮：
def factors(n):
gaps = [1,2,2,4,2,4,2,4,6,2,6]
length, cycle = 11, 3
f, fs, nxt = 2, [], 0
while f * f <= n:
while n % f == 0:
fs.append(f)
n /= f
f += gaps[nxt]
nxt += 1
if nxt == length:
nxt = cycle
if n > 1: fs.append(n)
return fs
Thus, print factors(13290059)will output [3119, 4261]. Factoring wheels have the same O(sqrt(n)) time complexity as normal trial division, but will be two or three times faster in practice.
因此，print factors(13290059)将输出[3119, 4261]. 因子轮具有与正常试验除法相同的 O(sqrt(n)) 时间复杂度，但在实践中会快两到三倍。
I've done a lot of work with prime numbers at my blog. Please feel free to visit and study.
我在我的博客上做了很多关于质数的工作。请随时参观和学习。
回答by Jonas Bystr?m
def factorize(n):
for f in range(2,n//2+1):
while n%f == 0:
n //= f
yield f
It's slow but dead simple. If you want to create a command-line utility, you could do:
它很慢但非常简单。如果要创建命令行实用程序，可以执行以下操作：
import sys
[print(i) for i in factorize(int(sys.argv[1]))]
回答by Mike Lisanke
Most of the above solutions appear somewhat incomplete. A prime factorization would repeat each prime factor of the number (e.g. 9 = [3 3]).
上述大多数解决方案似乎有些不完整。质因数分解将重复数字的每个质因数(e.g. 9 = [3 3])。
Also, the above solutions could be written as lazy functions for implementation convenience.
此外，为了实现方便，上述解决方案可以编写为惰性函数。
The use sieve Of Eratosthenesto find primes to test is optimal, but; the above implementation used more memory than necessary.
使用sieve Of Eratosthenes发现的素数测试是最佳的，但是，上面的实现使用了比需要更多的内存。
I'm not certain if/how "wheel factorization"would be superior to applying only prime factors, for division tests of n.
"wheel factorization"对于 n 的除法测试，我不确定是否/如何比仅应用素因数更好。
While these solution are indeed helpful, I'd suggest the following two functions -
虽然这些解决方案确实有帮助，但我建议使用以下两个功能 -
Function-1 :
功能-1：
def primes(n):
if n < 2: return
yield 2
plist = [2]
for i in range(3,n):
test = True
for j in plist:
if j>n**0.5:
break
if i%j==0:
test = False
break
if test:
plist.append(i)
yield i
Function-2 :
功能-2：
def pfactors(n):
for p in primes(n):
while n%p==0:
yield p
n=n//p
if n==1: return
list(pfactors(99999))
[3, 3, 41, 271]
3*3*41*271
99999
list(pfactors(13290059))
[3119, 4261]
3119*4261
13290059
回答by kadi
def get_prime_factors(number):
"""
Return prime factor list for a given number
number - an integer number
Example: get_prime_factors(8) --> [2, 2, 2].
"""
if number == 1:
return []
# We have to begin with 2 instead of 1 or 0
# to avoid the calls infinite or the division by 0
for i in xrange(2, number):
# Get remainder and quotient
rd, qt = divmod(number, i)
if not qt: # if equal to zero
return [i] + get_prime_factors(rd)
return [number]
回答by swopnilojha
from sets import Set
# this function generates all the possible factors of a required number x
def factors_mult(X):
L = []
[L.append(i) for i in range(2,X) if X % i == 0]
return L
# this function generates list containing prime numbers upto the required number x
def prime_range(X):
l = [2]
for i in range(3,X+1):
for j in range(2,i):
if i % j == 0:
break
else:
l.append(i)
return l
# This function computes the intersection of the two lists by invoking Set from the sets module
def prime_factors(X):
y = Set(prime_range(X))
z = Set(factors_mult(X))
k = list(y & z)
k = sorted(k)
print "The prime factors of " + str(X) + " is ", k
# for eg
prime_factors(356)
回答by Chris Cogdon
I've tweaked @user448810's answer to use iterators from itertools (and python3.4, but it should be back-portable). The solution is about 15% faster.
我已经调整了@user448810 的答案，以使用 itertools（和 python3.4，但它应该是可移植的）中的迭代器。该解决方案的速度提高了约 15%。
import itertools
def factors(n):
f = 2
increments = itertools.chain([1,2,2], itertools.cycle([4,2,4,2,4,6,2,6]))
for incr in increments:
if f*f > n:
break
while n % f == 0:
yield f
n //= f
f += incr
if n > 1:
yield n
Note that this returns an iterable, not a list. Wrap it in list() if that's what you want.
请注意，这将返回一个可迭代对象，而不是一个列表。如果这是您想要的，请将其包装在 list() 中。
回答by Amit Tripathi
Most of the answer are making things too complex. We can do this
大多数答案都使事情变得过于复杂。我们可以完成这个
def prime_factors(n):
num = []
#add 2 to list or prime factors and remove all even numbers(like sieve of ertosthenes)
while(n%2 == 0):
num.append(2)
n /= 2
#divide by odd numbers and remove all of their multiples increment by 2 if no perfectlly devides add it
for i in xrange(3, int(sqrt(n))+1, 2):
while (n%i == 0):
num.append(i)
n /= i
#if no is > 2 i.e no is a prime number that is only divisible by itself add it
if n>2:
num.append(n)
print (num)
Algorithm from GeeksforGeeks
来自GeeksforGeeks 的算法
