Combination 소인수 분해

Combination 은 다음 식으로 계산이 가능합니다.

 

nCr = n! / ((n-r)! * r!)

 

n, r 숫자가 커지면 결과가 너무 커져서 계산이 힘들어 집니다.

 

대신 계산을 끝까지 하지 않고도, 소인수 분해는 가능합니다.

 

아래 코드를 이용하면 됩니다.

 

def findPrimeFactors(n, k):
    tPrimeFactorsMap = {}
    
    # 소수인지 합성수인지 체크하기 위한 배열 - 최대 소수는 n 보다 작거나 같음
    tCompositeChecker = [True] * 2 + [False] * n
    
    for p in xrange(n + 1):
    
    	# 합성수인 경우 다음으로 넘김
        if tCompositeChecker[p]:
            continue
        
        q = p
        m = 1
        
        # 현재 소수 p가 몇 번 나오는지 체크하기 위한 변수
        tPrimeCnt = 0
        
        # 현재 체크 중인 q에 대해서 해당 소수 p가 몇 번 들어 있는지 체크하기 위한 리스트
        tPrimePowers = [0] * (n + 1)
        
        while True:
            tPrimePowers[q] = tPrimePowers[m] + 1
            
            # q 가 k 보다 작거나 같으면 분모, 해당 개수 만큼 빼줌
            if q <= k:
                tPrimeCnt -= tPrimePowers[q]
            # q 가 n - k 보타 크면 분자, 해당 개수 만큼 더해줌
            if q > n - k:
                tPrimeCnt += tPrimePowers[q]
                
            q += p
            m += 1
            if q > n:
                break
            
            # q는 p의 배수이므로 합성수
            tCompositeChecker[q] = True
            
        tPrimeFactorsMap[p] = tPrimeCnt
        
    return tPrimeFactorsMap