HJ6题解 | #质数因子#(得懂概念）

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    long num, temp;//int上下三万不够，要用long
    cin>>num;
    temp = num;
    if(num == 1)//正整数还有1
    {
        cout<<1;
        return 0;
    }

    for(long i=2; i<=sqrt(temp); i++)//一个数的质因数(除了最大的那个)不会超过它的算术平方根
    {
        while(num % i == 0)
        //求余为0，说明还有这个质因子
        //为什么4不会呢，因为4是合数，2、2已经被我们去了，所以从2往上找即可
        {
            cout<<i<<" ";
            num /= i;
        }
    }
    //如果找到算术平方根还没有能整除的就直接输出（本身就是质数）
    if(num != 1)//还没有被除过，或者除过剩下的最大质因子直接输出
    {
        cout<<num;
    }
}
//所有的合数都是由质数相乘得到的，只要一个数把质因数全部除掉，它就不会有合因数了。

HJ6，还是得懂得质数因子的求法。