题解 | #质数因子#

/*
#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能在评论区解释一下。