素数分解 - 列表

Question

我正在尝试实现一个函数primeFac(),该函数将正整数作为输入,n并返回包含素数因子分解中所有数字的列表n.

我已经做到这一点,但我认为在这里使用递归会更好,不知道如何在这里创建递归代码,什么是基本情况？首先.

我的代码:

def primes(n):
    primfac = []
    d = 2
    while (n > 1):
         if n%d==0:
             primfac.append(d)
    # how do I continue from here... ?

Answer 1

一个简单的试验部门:

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(或特殊套管的更小的素数并且在更少的可能除数上循环)循环.

Answer 2

这是一个基于理解的解决方案,它可能是最接近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缩进.

Answer 3

该primefac模块做了所有数学家们几个世纪以来开发的花哨技术因式分解:

#!python

import primefac
import sys

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

Answer 4

这是我的试验分区的分解版本,其中包括仅由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和奇数的改进是车轮分解,它使用潜在素数之间的一组循环间隙来大大减少试验分割的数量.在这里我们使用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))时间复杂度,但在实践中将快两到三倍.

我在我的博客上做过很多关于素数的工作.请随时访问和学习.

Answer 5

我已经调整了@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

请注意，这将返回一个可迭代对象，而不是一个列表。如果这是您想要的，请将其包装在 list() 中。

Answer 6

上述大多数解决方案似乎有些不完整。质因数分解将重复数字的每个质因数(e.g. 9 = [3 3])。

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

使用sieve Of Eratosthenes发现的素数测试是最佳的，但是，上面的实现使用了比需要更多的内存。

"wheel factorization"对于 n 的除法测试，我不确定是否/如何比仅应用素因数更好。

虽然这些解决方案确实有帮助，但我建议使用以下两个功能 -

功能-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

功能-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