题解 P1075 【质因数分解】
Stephen_Curry · · 题解
这题真的不难，只不过数据点有点坑，因此要多多留意（小心！！！）
大多数人首先想到的就是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;
}然鹅结果也并不尽如人意... ...
其实还有一种更简便的方法！
大家应该知道，约数是成对出现的（平方数除外），也就是说，一个数的第一小约数乘第一大约数相乘等于这个数，第二小约数乘第二大约数相乘也依然等于这个数！
因此，只要找出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;