题解 | #质数因子#

#include <iostream>
#include <unistd.h>
#include <vector>
using namespace std;

vector<int> primeFactors(int num)
{
    vector<int> factors;
    while(num%2 == 0){
        factors.push_back(2);
        num/=2;
    }  
    for(int i = 3; i * i <= num; i+=2){
        while(num % i == 0){
            factors.push_back(i);
            num /= i;
        }
    } 
    if(num > 1) factors.push_back(num);    
    return factors;
}



int main() {
    int num;
    cin >> num;
    vector<int> factors = primeFactors(num);
    for(auto factor : factors)
        cout << factor << ' ';

}

1. 从 2 开始，尝试将这个数不断地除以 2，直到它不能再整除为止。对于每一次整除，2 都是这个数的质因子之一。
2. 接下来，尝试除以下一个质数，即 3。重复这个步骤，直到除数大于被除数的平方根为止。因为如果被除数存在大于其平方根的质因子，那么它们会成对出现，一个小于或等于平方根，一个大于平方根。
3. 如果在上述步骤中，被除数仍然大于 1，那么这个被除数本身就是一个质因子。