[종만북] 간단한 소인수 분해 / 정수론 / Python 파이썬

[종만북] 간단한 소인수 분해 / 정수론 / Python 파이썬

 

[종만북] 간단한 소인수 분해 / 정수론 / Python 파이썬

 

2부터 (N ^ 0.5) 까지의 수를 더이상 나눠지지 않을 때까지 나누는 것으로 소인수 분해를 진행한다.

 

n이 소수 인 경우 (N ^ 0.5) 번 반복문을돌기 때문에 시간복잡도는 O(N ^ 0.5)가 된다.

# 간단한 소인수 분해 알고리즘
# 시간복잡도 O( N ** 0.5 )
def factorSimple(N):
    ret = []
    sqrtn = int(N ** 0.5)

    # 소수가 아닌 [2, N**0.5] 범위의 모든 정수로 시도
    for div in range(2, sqrtn+1):
        while(N % div == 0):
            N //= div
            ret.append(div)

    if (N > 1):
        ret.append(N)

    return ret


print(factorSimple(28))