Python递归程序对一个数进行素数分解

在递归情况下,prime\u factorize函数没有return语句——您希望在其最后一行调用“returnprime\u factorize(x/i,li)”。用一个素数试试(这样就不需要递归调用),看看它在这种情况下是否有效。

此外,您可能希望使签名类似于:

def prime_factorize(x,li=None):
    if li is None: li = []

否则,两次或多次调用时会得到错误的结果:

>>> prime_factorize(10)
[2, 5]
>>> prime_factorize(4)
[2, 5, 2, 2]
>>> prime_factorize(19)
[2, 5, 2, 2, 19]

def primeFact (i, f):
    if i < f:
        return []
    if i % f == 0:
        return [f] + primeFact (i / f, 2)
    return primeFact (i, f + 1)

>>> primeFact (300, 2)
[2, 2, 3, 5, 5]
>>> primeFact (17, 2)
[17]
>>> primeFact (2310, 2)
[2, 3, 5, 7, 11]

@Anthony正确地回答了你关于 print . 然而,根据所提供的几个技巧的精神,这里有一个使用尾部递归移除的简单重构:

def prime_factorize(x):
  li = []
  while x >= 2:
    until = int(math.sqrt(x))+1
    for i in xrange(2,until):
      if not x%i:
        li.append(i)
        break
    else:
      li.append(x)
      return li
    x //= i

这并没有解决关键的性能问题(big-O行为与原始解决方案相同)——但由于Python本身不进行尾部递归优化,因此学习手动执行非常重要。

'return thisfun(newargs)' 进入 args=newargs; continue 把整个身体放进一个 while True: “循环”是尾部递归优化的基本思想。在这里,我还将li设置为非arg(没有理由将其设置为arg),并在 while ,并避开了 continue 因为递归步骤无论如何都是在主体的末尾。

这个公式将是一个很好的基础,从中可以应用进一步的优化重构(sqrt避免、记忆化等),以达到更好的性能。

def prime_factorize( number ):
    def recurse( factors, x, n ):
        if x<2: return factors # 0,1 dont have prime factors
        if n > 1+x**0.5: # reached the upper limit
            factors.append( x ) # the only prime left is x itself
            return factors
        if x%n==0: # x is a factor
            factors.append( n )
            return recurse( factors, x/n, n )
        else:
            return recurse( factors, x, n+1 )
    return recurse( [], number, 2)

for num, factors in ((n, prime_factorize( n )) for n in range(1,50000)):
    assert (num==reduce(lambda x,y:x*y, factors, 1)), (num, factors)
    #print num, ":", factors

def primeFactorization(n):
    """ Return the prime factors of the given number. """
    factors = []
    lastresult = n
    while 1:
        if lastresult == 1:
            break

        c = 2

        while 1:
            if lastresult % c == 0:
                break

            c += 1

        factors.append(c)
        lastresult /= c

    return factors

好吗。

def Pf(n,i):

  if n%2==0:
        print(2)
        Pf(n/2,3)
  elif n<i:
      return 0

  else:

  
      if n%i==0:
        print(i)
        Pf(n/i,i)
      else:
        Pf(n,i+2)
n=int(input())
Pf(n,3)

查看此代码