파이썬 소인수 분해-목록

양의 정수 n 을 입력으로 받고 n <의 소인수 분해에있는 모든 숫자를 포함하는 목록을 반환하는 함수 primeFac () 을 구현하려고합니다. / code>.

여기까지 왔지만 여기서 재귀 코드를 만드는 방법을 모르고 여기서 재귀를 사용하는 것이 더 낫다고 생각합니다. 기본 사례는 무엇입니까? 시작하기.

내 코드 :

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 에 대해서만 반복 (또는 더 작은 소수를 특수 케이스로 처리하고 가능한 제수를 더 적게 반복)하여 쉽게 개선 할 수 있습니다.

 

참조 페이지 https://stackoverflow.com/questions/16996217