관련 질문이 math.stackexchange.com 에도 올라와있지만, 따로 명칭은 없다.
이것을 활용하면, ∑[n/i] 를 O(√n) 시간복잡도로 계산할 수 있다
나이브하게, 모든 i에 대해서 [n/i]를 구해서 더하면 O(n)이다
[n/i]=K가 되는 i의 범위 [x,y]를 찾는다. i의 최대값 y는 [n/[n/i]] 으로 구할수 있다. 이제 x≤i≤y 범위에서 ∑[n/i] 는 [n/x]*(y-x+1) 로 O(1)에 바로 계산할 수 있다. 이러한 범위가 O(√n)개이므로, 전체 값을 O(√n)에 계산가능.
코드는 이런식이 된다
answer = 0
while i <= num:
j = num // (num // i)
answer += num // i * (j - i + 1)
i = j + 1
return answer
이 방법은 이 식 자체를 계산하는 것 보다는, f([N/1])g(1)+f([N/2])g(2)+…+f([N/N])g(N) 을 구하는 용도로 확장해서 사용하는 것이 핵심이다. 예를 들어 모든 약수의 합을 구할때에는 Fear Factoring 처럼 구현한다
만약 이 식(=약수의 갯수)만 계산하는 것이 목적이라면, 다음의 공식을 활용해서 같은 O(√n)의 시간복잡도로 보다 간단하게 구할수 있다.
$\sum_{i=1}^n\lfloor\frac ni\rfloor=2\sum_{i=1}^k\lfloor\frac ni\rfloor-k^2$ for $k=\lfloor\sqrt n\rfloor$
코드는 이렇게 된다
sqrt = math.isqrt(num)
answer = 2 * sum(num // i for i in range(1, sqrt + 1)) - sqrt * sqrt