在O(N)中直到N的数的除数计数? [英] Count of divisors of numbers till N in O(N)?

问题描述

因此，我们可以使用筛子在O(NlogN)算法中计算从1到N的每个数字的除数:

So, we can count divisors of each number from 1 to N in O(NlogN) algorithm with sieve:

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)? 预先感谢.

Is there way to reduce it to O(N)? Thanks in advance.

推荐答案

这个怎么样?从素数2开始，并保留一个元组列表(k, d_k)，其中d_k是k的除数的数量，以(1,1)开头:

How about this? Start with the prime 2 and keep a list of tuples, (k, d_k), where d_k is the number of divisors of k, starting with (1,1):

for each prime, p (ascending and lower than or equal to n / 2):
  for each tuple (k, d_k) in the list:
    if k * p > n:
      remove the tuple from the list
      continue
    power = 1
    while p * k <= n:
      add the tuple to the list if k * p^power <= n / p
      k = k * p
      output (k, (power + 1) * d_k)
      power = power + 1
  the next number the output has skipped is the next prime
  (since clearly all numbers up to the next prime are
   either smaller primes or composites of smaller primes)

上面的方法还生成素数，依靠O(n)内存来继续查找下一个素数.拥有更高效，独立的素数流可以使我们避免将任何元组(k, d_k)附加到列表中的k * next_prime > n，并释放所有大于n / next_prime的内存.

The method above also generates the primes, relying on O(n) memory to keep finding the next prime. Having a more efficient, independent stream of primes could allow us to avoid appending any tuples (k, d_k) to the list, where k * next_prime > n, as well as free up all memory holding output greater than n / next_prime.

Python 代码

这篇关于在O(N)中直到N的数的除数计数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！