c++ - 找到数 n 小于 k 的除数的有效方法

Question

我已经这样做了：-

int divisors(int div, int i) {

    int ans = 0;
    for (int j = 1; j * j <= div; j++) {
        if (div % j == 0) {
            if (div / j == j && j < i)ans++;
            else {
                if (j < i && div / j < i) {
                    ans += 2;
                }
                else if (j < i) {
                    ans += 1;
                }
                else {
                    break;
                }
            }
        }
    }
    return ans;

}

但是这需要 O(sqrt(div)) 时间，我有办法优化这个吗？

标签： c++number-theory

Answer 1

你不能低于，O(sqrt(N))因为在最坏的情况下k = N，你将不得不遍历直到sqrt(N)