题解 | #质数因子#

#include <iostream>
#include <cmath>

//函数： 检查一个数是否为质数
bool isPrime(int num) {
    if (num <= 1) return false;
    if (num <= 3) return true;
    if (num % 2 == 0 || num % 3 == 0) return false;

    int sqrtNum = static_cast<int>(std::sqrt(num)) + 1;
    for (int i = 5; i < sqrtNum; i += 6) {
        if (num % i == 0 || num % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

//函数：找到并输出一个数的所有质因子
void printPrimeFactors(int num){
    //处理2作为因子的情况
    while (num % 2 == 0) {
        std::cout << 2 << " ";
        num /= 2;
    }

    //接下来考虑奇数因子
    for (int i = 3; i <= std::sqrt(num); i+=2) {
        //当i是因子时
        while (num % i == 0) {
            std::cout << i << " ";
            num /= i;
        }
    }
    //如果num有大于其平方根的因子，那么它本身就是一个质数
    if (num > 2) {
        std::cout << num << " ";
    }
}

int main() {
    int n;
    std::cin >> n;
    printPrimeFactors(n);
    return 0;
}