[python] 소인수분해

 

👀 소인수분해

: 자연수를 소인수의 곱으로 나타낸 것

예) 10을 소인수분해 : 10 = 2×5

⭐ 소인수 : 자연수의 인수 중 소수

⭐ 소수 : 약수가 1과 자기 자신 뿐인 자연수

 

✔️ 소인수분해 함수

 입력 n이 2이상일 때 {소수1: 갯수1, 소수2: 갯수2, ...}형태로 반환.

def factorization(n):
    a, result = 2, {}
    while n>1:
        while not n%a:
            if not a in result.keys():
                result[a] = 1
            else:
                result[a] += 1
            n //= a
        a += 1
    return result