Maintenance script: Repair batch-0002 pages from live compare

2026-03-27T00:16:03Z

Repair batch-0002 pages from live compare

← Older revision		Revision as of 00:16, 27 March 2026
Line 6:		Line 6:
	class Counter:		class Counter:
	def __init__(self):		def __init__(self):
	self._cache=[None] * 1000000		self._cache=[None] * 1000000

	def __call__(self,n):		def __call__(self,n):
Line 12:		Line 12:

	def count(self,n,start=0):		def count(self,n,start=0):
	value = self._cache[n]		value = self._cache[n]
	if value != None: return value+start		if value != None: return value+start

Line 19:		Line 19:
	if n % e ==0:		if n % e ==0:
	result = self.count(n/e,start+1)		result = self.count(n/e,start+1)
	self._cache[n] = result		self._cache[n] = result
	return result		return result

	result = start+1		result = start+1
	self._cache[n] = result		self._cache[n] = result
	return result		return result

Line 33:		Line 33:

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

imported>Unknown at 05:23, 7 February 2021

2021-02-07T05:23:15Z

New page

== Approach ==
일단 Factorial 이라는 점에서 해당 계산에 대해 다음과 같은 식을 만들어냄.
F(n) = Count(n) + F(n-1)
Count(n) = 해당 n 에 대한 인수항 총합
그리고 F, Count 들에 대해서 caching 을 진행할 수 있으리라 생각, 다음과 같이 풀음.
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 를 떠날 때가 되었구나.;;

FactorialFactors/1002 - Revision history

Maintenance script: Repair batch-0002 pages from live compare

imported>Unknown at 05:23, 7 February 2021