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 를 떠날 때가 되���구나.;;