코드노예

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

보통 팩토리얼의 경우 숫자가 너무 커지기 때문에 정확한 값을 계산할 수 없는 경우가 많습니다.

하지만 팩토리얼 값을 소인수 분해했을 때, 지수가 어떻게 되는 지는 계산이 가능합니다.

다음 링크에서 자세한 설명을 보실 수 있습니다.

https://janmr.com/blog/2010/10/prime-factors-of-factorial-numbers/

특정 소수에 대한 지수를 계산하는 코드는 다음과 같습니다.

import math

def factorialExp(n, p):
    tRet = 0
    tVal = int(math.log(n, p))
    for i in xrange(1, tVal+1):
        tRet += n // p**i
    return tRet