O(N) 中直到 N 为止的数字的约数计数？

因此，我们可以使用 sieve 在 O(NlogN) 算法中计算从 1 到 N 的每个数字的约数：

int n;
cin >> n;
for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j += i) {
        cnt[j]++; //// here cnt[x] means count of divisors of x
    }
}

有没有办法减少到O(N)？ 提前致谢。

这是对@גלעדברקן解决方案的简单优化。不要使用集合，而是使用数组。这大约是设定版本的 10 倍。

n = 100

answer = [None for i in range(0, n+1)]
answer[1] = 1

small_factors = [1]
p = 1
while (p < n):
    p = p + 1
    if answer[p] is None:
        print("\n\nPrime: " + str(p))
        limit = n / p
        new_small_factors = []
        for i in small_factors:
            j = i
            while j <= limit:
                new_small_factors.append(j)
                answer[j * p] = answer[j] + answer[i]
                j = j * p
        small_factors = new_small_factors

print("\n\nAnswer: " + str([(k,d) for k,d in enumerate(answer)]))

值得注意的是，这也是一个 O(n) 的素数枚举算法。然而，通过使用由所有小于尺寸的素数生成的轮子log(n)/2它可以及时创建一个素数列表O(n/log(log(n))).