题解 | #质数因子#
质数因子
https://www.nowcoder.com/practice/196534628ca6490ebce2e336b47b3607
/*
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int num;
cin >> num;
int k = sqrt(num);
for (int i = 2; i <= k; i++) {
while (num % i == 0) {
cout << i << " ";
num = num / i;
}
}
if (num != 1) {
cout << num << " ";
}
}*/
#include <iostream>
#include <cmath>
using namespace std;
bool isZ(int x) {
for (int i = 2; i <= sqrt(x); i++) {
if (x % i == 0 && x != i) {
return false;
}
}
return true;
}
int main() {
int num;
cin >> num;
int last_num = num;
for (int i = 2; i <= sqrt(last_num); i++) {
if (isZ(i)) {
while (num % i == 0) {
cout << i << " ";
num = num / i;
}
}
}
if (num != 1) {
cout << num << " ";
}
}
参考了一下各种写法；
重要的知识点有2个
1.寻找因数只需要找到本数的平方根处即可，这可以减小时间复杂度；使用cmath头调用了sqrt()函数进行开放；有个需要注意的地方，如果本身就是质数，这样的方法会漏掉本身这个因数，所以要记得进行判断。
2.不知道是不是偷鸡，其实判断除数是不是质数这步是多余的，实际上2个方法都能通过，为了符合题意我还是保留了这个判断质数的函数和步骤，希望有dalao能在评论区解释一下。
华为机试刷题记录 文章被收录于专栏
记录一下手打代码的解题思路方便复习
查看7道真题和解析
投递摩尔线程等公司10个岗位