1 <= x <= N에 대해 1이상 N이하의 모든 kx(k는 정수)를 순회하는 것 O(N^2)이 아니다.

망상을 하다 발견해서 까먹기전에 적어본다.

N = int(input())
for i in range(1,N+1):
    j = 1
    while i*j <= N:
    	j += 1

이 코드의 복잡도는 무엇일까.

순회한다면 O(N + (N/2) + (N/3) + ... + (N/N)) = O(N(1 + 1/2 + 1/3+...+ 1/N))의 복잡도일 것이다.

1/x꼴의 합을 조화급수라한다. 이는 정확한 값을 구할 수 없다. 하지만 근사가 가능하다.

1 + 1/2 + 1/3 + ... + 1/N은 lnN + γ 이다.

ln은 자연로그이고 그 밑은 e = 2.71828...이다. γ는 오일러 상수라 부르고 0.57721...이다.

따라서 복잡도는 O(N(lnN + γ))가 된다.

N(lnN + γ)는 

N이 1만일때 약 9만8천 

N이 5만일때 약 57만

N이 10만일때 약 121만

N이 20만일때 약 256만

N이 100만일때 약 1439만

이다.