质因数分解(思维训练)

在讲这道 NOIP 真题之前，我们先来聊聊质因数分解，这是本周 的思考题： 输入一个正整数 n，把它分解成质因子相乘的形式，如 36 = 1 * 2

2 * 3 * 3；19=1 * 19.（1 不是质因数，这里带上1只是一种表 示的格式）

当前要考察的质因数是3，为什么原数除到 5 之后就可以结束运算 了呢？因为，一个数的质因数不会超过它自己的平方根，开平方 会导致精度的丢失，所以更简单的判别方法是质因数的平方不会 超过数字本身，3*3 > 5 了，所以可以终止运算了，按照我们的题 目要求 360 输出的表示法是： 360=1 * 2 * 2 * 2 * 3 * 3 * 5；

题目描述 已知正整数 n 是两个不同的质数的乘积，试求出较大的那个质 数。 输入 每组输入数据只有一行，包含一个正整数 n。 数据规模： 对于60%的数据，6≤n≤1000。 对于100%的数据，6≤n≤2*10^9。 输出 每组输出只有一行，包含一个正整数 p，即较大的那个质数。

题解：

如果你已经搞定了上一篇文章的题目，你会发现这道真题非常的 简单。重点是要搞清楚题目描述的数字 n 的构成。我在上一节课 中讲解过，一个数字的质因数分解是唯一的，唯一解的问题处理 起来会更简单，所以千万不要想的太复杂。 关键字我已经标红了，“两个不同” 这四个字透露的信息如下： 1.分解得到的质因数，有且只有两个数字 2.每个数字都只有 1 个 符合题意的数字的表达式一定是下面这样的： 6 = 2 * 3 10 = 2 * 5 15 = 3 * 5 21 = 3 * 7 … 而上一篇文章中的例子 36 = 2 * 2 * 3 * 3 虽然最终分解出的数字只有 2 和 3，但是 2 和 3 分别有 2 个，所 以不符合题意。如果修改题意，只限定质因数的数字而不限定每 个数字的数量的话，那么 36 就变成符合题意的数字了。 这题在计算时也有一些优化的技巧 解法 1：把这题当做一个完整的质因数分解的题目：从 2 开始尝 试，先找到较小的那个质因数，然后标记一下找到较小的质因数 了，继续寻找第二个质因数，一旦找到就能确定该质因数是较大 的那个。 解法 2：把这题当做寻找最小质因数的题目：从 2 开始尝试，找 到较小的那个质因数，比如是 a ，那么较大的质因数直接通过公 式 n / a 就可以得到，避免了多余的运算。 显然解法 2 更优，那我们就来看看解法 2 吧。

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n,i=2;
cin>>n;
while(i*i<=n) {
//每一次循环都需要做点事情
if(n%i == 0) {
//如果能整除，打印出来n/i
cout<<n/i;
//直接返回就行了
return 0;
}
i++;
}
return 0;
}