算法

(枚举,数学) $O(\sqrt n)$

所有约数都是成对出现的：如果 $d$ 是 $n$ 的约数，那么 $\frac{n}{d}$ 也是 $n$ 的约数。

我们可以只枚举较小的约数，然后计算出较大的约数即可。那么需要枚举的范围满足： $d \le \frac{n}{d}$，则 $d \le \sqrt n$。因此只需要枚举 $\sqrt n$ 次。

时间复杂度

由于只枚举较小的约数，所以只需枚举 $\sqrt n$ 次，因此总时间复杂度是 $O(\sqrt n)$。

C++ 代码

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    for (int i = 2; ; i ++ )
        if (n % i == 0)
        {
            cout << n / i << endl;
            break;
        }

    return 0;
}