HJ6 题解 | #质数因子# 回顾质数，因数的判定

#include<iostream>
using namespace std;

//判断1个数是否为质数
bool isPrime(int num) {
    if (num <= 1) {
        return false;
    }
    if (num == 2) {
        return true;
    }
    if (num % 2 == 0) {
        return false;
    }
    int i = 3;
    while (i * i <= num) {
        if (num % i == 0) {
            return false;
        }
        i += 2;
    }
    return true;
}

int main() {
    int num;
    int p[1000]; //数组用来存储质数因子
    cin >> num;
    if (isPrime(num)) {       //先判断数本身是不是质数
        cout << num;
        return 0;
    }
    int num2 = num / 2;     //一个数的因数不会超过自身大小的一半
    int i = 2;
    int k = 0;
    int j = 0;          //记录因数个数
    while (i <= num2) {  //循环不超过数本身大小的一半
        if (num % i == 0) { 
            if (isPrime(i)) {   //判断因数i是否是质数
                p[j] = i;      //是的话加入到p数组
                j++;
                k = num / i;   //因数i对应的另一个因数k
            }
             
            if (isPrime(k)) {   //i不是质数不会执行
                p[j] = k;
                j++;    
                break;     //1个因数是质数，对应的因数也是质数，则肯定不会有其他因数了
            }
            num = num / i; 
        } else {
            i++;
        }
    }

    for (int i = 0; i < j; i++)
        cout << p[i] << ' ';


    return 0;
}