带循环的 C++ 除数代码

Question

我在 coderforces 上遇到了一个名为除数的问题。

我相信我已经解决了它，但它给了我一个超出时间限制错误，所以我尽力让它更短但仍然是同样的错误。

在这个问题中，我必须给出数字应该有多少个除数。

我的代码是:

#include <iostream>
using namespace std;
int main(){
    long long  t, x;
    int res = 2;
    cin >> t;

    for (int j = 0; j < t; j++){
        cin >> x;
        for (int i = 2; i <= x / 2; i++){
            if (x%i == 0){
                res++;
            }
        }
        cout << res << endl;
    }
    return 0;
}

示例输入应该是:

3

12

7

36

输出应该是:

6

2

9

Answer 1

您可以根据当前数字是奇数还是偶数，在两种不同的情况下“拆分”您的内部循环(计算当前数字的除数的循环):如果它是奇数，那么您只需要检查奇数除法，从 3 开始。

无论如何，您可以通过仅检查从 2 到 floor(sqrt(x)) 的数字来进一步优化内部循环。如果一个数字 x 可以被 i 整除，那么它也可以被 x/i 整除，所以检查从 2 到 x/2，只查找直到 (int) sqrt(x)(不是绝对需要转换 sqrt 的结果，因为 i 是 int)。

内部循环的代码可能如下所示:

for (int i = 2; i <= (int)sqrt(x); i++) {
    if (x % i == 0)
        res += 2;
}