题解 | 质因数分解-NOIP2012普及组复赛

算法：枚举,数学

复杂度： $O(\sqrt n)$

解题思路：

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

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

另外，牛客暑期NOIP真题班限时免费报名
报名链接：https://www.nowcoder.com/courses/cover/live/248
报名优惠券：DCYxdCJ