Factorial Factors/1002

������ Factorial ��������� ��������� 해��� ��������� ���해 ��������� ������ ������ ������������.

F(n) = Count(n) + F(n-1)
Count(n) = 해��� n ��� ���한 ������항 ���합

��������� F, Count ������ ���해��� caching ��� ���행할 ��� ������������ ������, ��������� ������ �����.

~cpp
class Counter:
    def __init__(self):
        self._cache=[None] * 1000000

    def __call__(self,n):
        return self.count(n)

    def count(self,n,start=0):
        value = self._cache[n]
        if value != None: return value+start
        
        half = n/2
        for e in xrange(2,half+1):
            if n % e ==0:
                result = self.count(n/e,start+1)
                self._cache[n] = result
                return result
        
        result = start+1
        self._cache[n] = result
        return result

CountFunc = Counter()

def factorialFactor(n):
    total = sum((CountFunc(i) for i in xrange(2,n+1)))
    return total

def main():
    for i in [2,5,8,1996,123456,1000000]: print factorialFactor(i)

• �������� 해��� C++ ��� ��������� ��������������� (������ ������������ 5���) 100��� ���하��������� 12��� ������ ������.
  
  • ��������������� ��������� ������ Counter ��������� O(n^2) ������. caching ��� 함������ ������������ ������ ��������� ������ ������������ ������������.
    
  • Python ������ O(n^2) ��� ��������������� C++ ��������� O(n^2) ������.
    ��������� Python ������ 5��� ������ ������ ��������������� ������������ C++ ��� 1��� ��������� ��������� ������ ���������.
    


• ��태��� ������������ ������ ������ ������하���. ������ ZP ��� ������ ������ ������������.;;