一个简单的审判部门:
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
(或特殊情况下将更多小质数并在可能的除数上循环)来轻松改进它。