P1075 质因数分解
对应章节：五、数据结构与算法 → （五） 基础数论。
（一） 任务与输出目标
一个数是两个不同质数的乘积，求较大的质因数。
（二） 建模与推导
较小质因数不超过平方根。从 2 开始试除，第一次找到因子 d 时，它就是较小质数：合数因子的更小质因数早已被找到。较大质数为 n/d。
（三） 手算与过程
n=21，首次找到 d=3，输出 7。
（四） 带注释实现
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
int n;
cin >> n;
for (int d = 2; d * d <= n; ++d)
if (n % d == 0) {
cout << n / d << '\n';
break;
} // 两因子中较大的是商。
}
signed main() {
ios::sync_with_stdio(false); // 关闭同步，使用 cin 与 cout 完成输入输出。
cin.tie(0), cout.tie(0);
int T = 1; // 本题读入一组数据。
// cin >> T; // 题目给出测试组数时开启，并在 solve 中处理一组。
while (T--)
solve();
}（五） 复杂度
时间 \(O(\sqrt n)\)，额外空间 \(O(1)\)。