P1075 [NOIP2012 普及组] 质因数分解
[NOIP2012 普及组] 质因数分解
题目描述
已知正整数 n 是两个不同的质数的乘积，试求出两者中较大的那个质数。
输入格式
输入一个正整数 n。
输出格式
输出一个正整数 p，即较大的那个质数。
样例 #1
样例输入 #1
21
样例输出 #1
7
说明/提示
1 ≤ n≤ 2× 10^9
NOIP 2012 普及组 第一题
分析
这题真的不难，只不过数据点有点坑，因此要多多留意（小心！！！）
大多数人首先想到的就是for循环从(n - 1)一直枚举下去，贴代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = n - 1; i >= 2; i--) if (n % i == 0) {
cout << i;
break;
}
return 0;
}
可是这样的结果是... ...
有人说，其实没必要枚举到2，枚举到n的平方根就行了。
代码见下：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = n - 1; i > sqrt(n); i--) if (n % i == 0) {
cout << i;
break;
}
return 0;
}
然鹅结果也并不尽如人意... ...
其实还有一种更简便的方法！
大家应该知道，约数是成对出现的（平方数除外），也就是说，一个数的第一小约数乘第一大约数相乘等于这个数，第二小约数乘第二大约数相乘也依然等于这个数！
（如28的第一小约数是2，第一大约数是14；28的第二小约数是4，第二大约数是7）
因此，只要找出n的最小约数（1除外），再用n除以这个数，就能得到结果了！
贴上代码：
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 2; i <= n; i++) if (n % i == 0) {
cout << n / i;
break;
}
return 0;
}
终于通过了... ...
其实，中间的for循环也可以改成while循环，核心代码见下：
while (i <= sqrt(n)) {
if (n % i == 0) break;
i++;
}
cout << n / i;