素数分解 - 列表 [英] Prime factorization - list

问题描述

我正在尝试实现一个函数 primeFac()，该函数将一个正整数 n 作为输入，并返回一个包含 n.

I am trying to implement a function primeFac() that takes as input a positive integer n and returns a list containing all the numbers in the prime factorization of 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.

我的代码:

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

推荐答案

一个简单的试划分:

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(或特殊情况下更多小素数并循环较少可能的除数)来轻松改进它.

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

这篇关于素数分解 - 列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！