c++ - 如何找到时间复杂度小于 N 的给定数字 N 的所有因子？

Question

我正在尝试这个，但在输入>10000 这个循环 ID 时需要更多时间。

有什么方法可以优化这个时间复杂度小于 N 或 (logn) 的方法吗？

#include <iostream>

using namespace std;

int main(int argc, char* argv[]) {
    int n = 10001;

    for (int i = 1; i < n; i++) {
        if (n % i == 0) {
            cout << i;
        }
    }
    return 0;
}

Answer 1

除了dmh2000's answer :您可以在检查中利用冗余。例如，如果一个数不能被 n 整除，它也不能被 n 的任何倍数整除。例如，不能被 2 整除的数也不能被 4、6 或 8 整除。

这种技术被称为 sieving .