题解 | #质数因子#

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

unsigned int ret_zhishu(unsigned int& zhishu);
bool panduan(unsigned int);

int main() {
    unsigned int num;
    cin >> num;
    vector<unsigned int> arr;
    unsigned int zhishu = 2;
  	//	先判断这个数是否为质数，如果是，那么质因子只有他自己，可以降低时间复杂度
    if (panduan(num)) {
        arr.push_back(num);
    } else {

        /*
            这个地方，上限设置为这个数的开方
            好处:
                能够降低时间复杂度
                如果该数字除以较小的质因子后的结果是个大质数，那么不会重复放进去
                    因为到不了另一边
        */     
        for (int i = 0; i <= sqrt(num); ++i) {
            //  先看能不能直接除，不能就在求下一个质数再继续除
            if (num % zhishu == 0) {
                num /= zhishu;
                if (panduan(num) && num != 1) {
                    arr.push_back(num);
                }

                //  有些数会重复放入，思考如何解决
                arr.push_back(zhishu);

                //  除完当前质数，看看数字有没有变成1，变成了就结束
                if (1 == num) {
                    break;
                }
            } else { //  获取下一个质数
                zhishu = ret_zhishu(zhishu);
            }
        }
    }


    vector<unsigned int>::iterator iter;

    sort(arr.begin(), arr.end());

    for (iter = arr.begin(); iter != arr.end(); ++iter) {
        cout << *iter << ' ';
    }
}
//  判断当前数是否为质数
bool panduan(unsigned int zhishu) {
    bool flag = true;
    for (int j = 2; j < sqrt(zhishu) + 1; j++) {
        if (zhishu % j == 0) {
            flag = false;
            break;
        }
    }
    return flag;
}

//  获取下一个质数
unsigned int ret_zhishu(unsigned int& zhishu) {
    bool flag = true;
    while (1) {
        ++zhishu;
        flag = panduan(zhishu);
        if (flag) {
            return zhishu;
        }
    }
}
// 64 位输出请用 printf("%lld")