问题描述
我正在尝试实现一个函数 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).
这篇关于素数分解 - 列表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!