python:素因数分解-列表

一个简单的试验部门：

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

与 O(sqrt(n)) 复杂性（最坏的情况）.您可以通过特殊外壳2并仅在奇数 d上循环来轻松改进它 （或使用特殊大小写的小质数，并循环使用较少的除数）。

这是一个基于理解的解决方案，它可能是您可以在Python中使用的最接近递归解决方案的方法 大量。

您可以使用一行获得适当的除数：

divisors = [ d for d in xrange(2,int(math.sqrt(n))) if n % d == 0 ]

然后我们可以测试除数中的数字是否为质数：

def isprime(d): return all( d % od != 0 for od in divisors if od != d )

测试其他除数是否除以d。

然后我们可以过滤素数除数：

prime_divisors = [ d for d in divisors if isprime(d) ]

当然，它可以组合成一个函数：

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 ) ]

在这里，\可以在不打断Python缩进的情况下打破界限。

primefac模块使用了数个世纪以来数学家开发的所有精美技术进行分解：

#!python
import primefac
import sys
n = int( sys.argv[1] )
factors = list( primefac.primefac(n) )
print '\n'.join(map(str, factors))

这是我通过试验除法进行因式分解的版本，它结合了仅除以2和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

将试验除以2和奇数的改进是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

因此， print factors(13290059) 将输出 [3119, 4261] .分解因子轮的O（sqrt（n））时间复杂度与普通试验除法一样，但是在实践中会快两倍或三倍。

我在博客上做了很多有关质数的工作.请随时访问和学习.

大多数上述解决方案似乎都不完整.素数分解将重复数 (e.g. 9 = [3 3])的每个素数 .

此外，为了实现方便，上述解决方案可以写为惰性函数.

使用 sieve Of Eratosthenes 找到要测试的素数是最佳的，但是； 上面的实现使用了不必要的内存.

我不确定是否/如何 对于n的除法检验将优于仅应用素因数。

虽然这些解决方案确实有帮助，但我建议以下 "wheel factorization"

two functions -

Function-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 :

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