求一个数的因子

发表于 分类于 阅读次数： 本文字数： 319 阅读时长 ≈ 1 分钟

暴力解法

对1~n进行枚举

1
2
3
4
5
for (int i = 1; i <= n; ++i) {
    if (n % i == 0) {
        cout << i << endl;
    }
}

这个时候，时间复杂度为O(n)

优化

当n % i == 0且i * i < n，n / i为n的一个因子。由此，我们可以做如下的优化：

1
2
3
4
5
6
7
for (int i = 1; i * i <= n; ++i) {
    if (n % i != 0) continue;
    cout << i << endl;
    if (i * i < n) {
        cout << n / i << endl;
    }
}

时间复杂度就降为了O(sqrt(n))